LeetCode #46 Permutations

https://leetcode.com/problems/permutations/

문제파악

Given a collection of distinct integers, return all possible permutations.
주어진 중복이 없는 숫자 모음을 가지고 모든 조합을 구하라.

예제파악

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

간단한 예제이다.
이 예제로 가능한 조합을 트리로 그리면 다음과 같다.

백트랙킹 템플릿은 다음과 같다.

function dfs(node, state):
    if state is a solution:
        report(state) # e.g. add state to final result list
        return

    for child in children:
        if child is a part of a potential solution:
            state.add(child) # make move
            dfs(child, state)
            state.remove(child) # backtrack

이 템플릿을 토대로 코드를 짜면 다음과 같다.

코드

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    let answer = [];

    go([], new Array(nums.length).fill(false));

    function go(arr, checked) {
        if(arr.length === nums.length){
            answer.push(Array.from(arr)); // deep copy
            return;
        }

        for (let i = 0; i < nums.length; i++) {
            if(checked[i]){
                continue;
            }

            const el = nums[i];
            arr.push(el);
            
            checked[i] = true;

            go(arr, checked);
            
          	// backtrack
            arr.pop();
            checked[i] = false;

        }
    }

    return answer;
};

참고

https://leetcode.com/problems/permutations/discuss/685868/DFSbacktracking-PythonJavaJavascript-PICTURE
https://algo.monster/problems/backtracking