46. Permutations

46. Permutations

문제

입력받은 nums 배열의 가능한 모든 순열을 생성하기 위해서 재귀적으로 permuted 함수를 호출한다. 1부터 n까지 k자리수까지 조합 만들기 문제를 응용해서 접근해 보았다.

테스트 케이스

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

풀이

1. 먼저, 모든 순열을 저장할 permutations 배열을 만든다.
2. permuted 함수를 정의한다.
3. remaining 배열이 빌 때까지 재귀 호출을 반복한다.
4. remaining[i]를 permutation에 저장하고, i번째 숫자를 제외한 나머지 요소는 remaining으로 전달한다. [...remaining.slice(0, i), ...remaining.slice(i + 1)]
5. remaining 배열에 요소가 없으면 permutation 조합이 담긴 배열을 permutations에 푸시한다.
6. permutations 배열을 반환한다.

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
  const permutations = []

  var permuted = (permutation, remaining) => {
    if (remaining.length === 0) {
      permutations.push(permutation)
    } else {
      for (let i = 0; i < remaining.length; i++) {
        const num = remaining[i]
        permuted([...permutation, num], [...remaining.slice(0, i), ...remaining.slice(i + 1)])
      }
    }
  }

  permuted([], nums)
  return permutations
};