[leetCode/JS] 46. Permutations

문제 설명

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

 

 

입출력 예

Example 1:

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

 

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

 

Example 3:

Input: nums = [1]
Output: [[1]]

 

Constraints

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

---

내 솔루션

• DFS로 풀었다.

var permute = function(nums) {
  const answer = [];
  const dfs = (cur, rest) => {
    if(rest.length === 0) {
      answer.push(cur);
      return;
    }
    for (let i = 0; i < rest.length; i++) {
      dfs([...cur, rest[i]], [...rest.slice(0, i), ...rest.slice(i + 1)]);
    }
  }
  dfs([], nums);
  return answer;
};

최고의 솔루션

• 내가 푼 방법과 방식은 똑같으나 Set을 사용했다.
• 내가 121ms 걸렸는데, 이 방법은 78ms 가 걸렸다.

var permute = function(nums) {
  const output = []
  const recursion = (permutation, set) =>{
    if(set.size === 0){
      output.push(permutation)  
      return
    } 
    for(let val of set){
      const setCopy = new Set(set)
      setCopy.delete(val)
      recursion([...permutation, val], setCopy)
    }
  }
  recursion([], new Set(nums))
  return output
};

 

감상평

• DFS의 기본! 수열!