문제

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
모두 다른 정수로 이루어진 배열이 주어졌을 때, 만들 수 있는 모든 순열을 리턴하라.

입출력 예

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

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

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

제한 조건

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.
모든 정수는 중복되지 않는다.

---

풀이

backtracking(역추적) & DFS(깊이우선탐색)를 이용해 풀어야 한다.

백트래킹 패턴

1. 반복 - 주어진 input 엘리먼트에 반복문을 돌린다.
2. 선택 - 탐색 타겟을 선택해 엘리먼트의 순서를 교체한다.
3. 탐색 - DFS를 사용해 탐색한다.
4. 선택 취소 - 선택 과정을 다시 복구한다(restore)

function permutate(arr) {
  const result = []; // 결과값을 저장할 배열
  
  // DFS 함수
  const dfs = (i, arr) => {
    // base condition
    if (i === arr.length) {		    // index가 arr의 길이와 같아지면
      return result.push([...arr]); // 결과값에 푸시해준다.
    }
    
    // 범위를 선택해 반복문을 돌려준다.
    for (let j = i; j < arr.length; j++) {
      // swap
      [arr[i], arr[j]] = [arr[j], arr[i]];
  	  // swap한 범위를 가지고 dfs해준다.
      dfs(i + 1, arr); // 이때, i는 픽스되고 i를 뺀 나머지 값을 전달한다.
      // swap back
      [arr[i], arr[j]] = [arr[j], arr[i]]; // swap했던 arr를 원상복귀 해주며 깊이에서 빠져나온다.
    }
  }
  
  // entry point
  dfs(0, arr);

  return result;
}