[LeetCode] 46. Permutations

https://leetcode.com/

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.

 

Code :

var permute = function(nums) {
    // 결과를 저장할 배열을 초기화합니다.
    const result = [];
    
    // 백트래킹 함수를 정의합니다.
    const backtrack = (current, remaining) => {
        // 기저 조건: 남은 배열이 없을 경우 결과에 추가합니다.
        if (remaining.length === 0) {
            result.push(current);
            return;
        }
        
        // 남은 배열의 각 요소에 대해 순회합니다.
        for (let i = 0; i < remaining.length; i++) {
            // 현재 요소를 포함한 새로운 배열과 남은 요소들을 구합니다.
            const newCurrent = [...current, remaining[i]];
            const newRemaining = remaining.filter((_, index) => index !== i);
            // 재귀적으로 백트래킹 함수를 호출합니다.
            backtrack(newCurrent, newRemaining);
        }
    };
    
    // 초기 호출을 수행합니다.
    backtrack([], nums);
    // 결과를 반환합니다.
    return result;
};

 

Solutions Code :

var permute = function(letters) {
    // 결과를 저장할 빈 배열 res를 생성합니다.
    let res = [];
    // dfs 함수를 호출하여 순열을 생성하고 res 배열에 저장한 후, res 배열을 반환합니다.
    dfs(letters, [], Array(letters.length).fill(false), res);
    return res;
}

function dfs(letters, path, used, res) {
    // 현재까지의 순열이 letters 배열의 길이와 동일하다면, 모든 요소를 사용한 것이므로
    // 순열을 결과 배열 res에 추가하고 함수를 종료합니다.
    if (path.length == letters.length) {
        res.push(Array.from(path));
        return;
    }

    // letters 배열의 각 요소에 대해 반복합니다.
    for (let i = 0; i < letters.length; i++) {
        // 이미 사용한 요소라면 건너뛰고 다음 요소를 확인합니다.
        if (used[i]) continue;
        // 현재 요소를 순열 경로 path에 추가하고, 해당 요소를 사용되었음을 표시합니다.
        path.push(letters[i]);
        used[i] = true;
        // 재귀적으로 dfs 함수를 호출하여 나머지 순열을 생성합니다.
        dfs(letters, path, used, res);
        // 다음 순열을 생성하기 위해 현재 요소를 순열에서 제거하고, 사용되지 않았음을 표시합니다.
        path.pop();
        used[i] = false;
    }
}

 

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode