46. Permutations

늘보·2021년 11월 1일

LeetCode

목록 보기

66/69

💡 풀이

var permute = function (nums) {
  let answer = [];

  const backTracking = (level, letters) => {
    console.log('letters: ', letters);
    if (level === nums.length) {
      answer.push([...letters]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (letters.includes(nums[i])) continue;
      letters.push(nums[i]);
      backTracking(level + 1, letters);
      
      // BackTrack
      letters.pop();
    }
  };

  backTracking(0, []);

  // console.log('answer: ', answer);
  return answer;
};

let nums = [1, 2, 3];
permute(nums);
// BackTracking은 가능성을 탐색하는 알고리즘
// ex) [_, _, _] 이렇게 3개의 공간에 가능성을 채워 나가보자.

📝 결과

BackTracking 알고리즘을 알기 전까지 오직 재귀함수로만 풀어보려고 했던 지난날.. (수많은 Runtime Error와 함께)

📝 정리

BackTracking 알고리즘 관련 문제들을 연습중이다. 그 중 대표적인 '순열'을 구현할 수 있냐고 묻는 문제였다. 그럼 순열이 뭔지 먼저 보자.

순열은 서로 다른 n개의 원소에서 r개를 뽑아서 한 줄로 세우는 경우의 수를 말한다. 여기서 r, n은 자연수이며, r은 n이하여야만 한다.
또한 순열은 정의역과 공역이 같은 일대일 대응이다. 여기서 일대일 대응은 두 집합 사이를 중복 없이 모두 일대일로 대응시키는 함수를 말한다.
순열에 대해 좀 더 자세한 설명은 다음 블로그를 참고하자.

그럼 이제 다음 그림을 보자.

먼저, a를 선택했다고 가정할 경우, 그 다음 level에서는 b와 c를 탐색할 수 있다.
그리고 다음에 a,b를 탐색했다면 그 다음 level에서는 오직 c만 탐색할 수 있다.
또 다른 경우를 보자. a,c를 탐색했다면 그 다음 level에서는 오직 b만 탐색할 수 있다.
코드는 지금까지의 BackTracking 알고리즘 관련 문제와 큰 차이가 없다.
만약, nums 배열의 길이와 같은 depth만큼 level을 탐색했다면?(=그러니까 끝까지 탐색했다면!)

 if (level === nums.length) {
      answer.push([...letters]);
      return;
 }

다음과 같이 경우의 수에 해당하는 letters 배열을 복사해서 answer에 넣어주면 된다.

 for (let i = 0; i < nums.length; i++) {
      if (letters.includes(nums[i])) continue;
      letters.push(nums[i]);
      backTracking(level + 1, letters);
      
      // BackTrack
      letters.pop();
 }

경우의 수를 탐색하는 부분은 다음과 같다. 단계마다 순차적으로 파라미터가 변화하는데, level의 경우 1씩 더해주고, letters 배열의 경우 nums[i]를 계속 push해준다.
그리고 letters가 다른 경우도 탐색해야 하기 때문에(BackTrack), letters.pop()을 해준다.