[LeetCode] 46. Permutations

01.03.2024

1. Problem

2. Before

2-1. My Code

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    const len = nums.length;
    let result = [];

    result.push(nums);
    result.push(nums.reverse());

    for(var i = 0; i < len; i++ ) {
        for(var j = 0; j < len-1; j++){
            nums[j+1], nums[j] = nums[j], nums[j+1];
            if (!(nums in result)) result.push(nums);
        }   
    };
    console.log(result);

    return result;
};

2-2. Result

[[3,2,1],[3,2,1],[3,2,1],[3,2,1],[3,2,1],[3,2,1],[3,2,1],[3,2,1]]

As seen, the result was wrong.

2-3. What I Learned

1. BackTracking (My code didn't cover all the cases and had to be changed to BackTracking)
2. Deep Copy vs Shallow Copy (With Spread Operator and Slice(0))
3. How to Swap in JS

3. Final Code (After Viewing Other Solutions)

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    const result = [];
    backtrack(nums, result);
    return result;
};

function backtrack(arr, res, n = 0) {
    if (n === arr.length - 1) {
        res.push(arr.slice(0));
        return;
    }
    for (let i = n; i < arr.length; i++) {
        [arr[i], arr[n]] = [arr[n], arr[i]];
        backtrack(arr, res, n + 1);
        [arr[i], arr[n]] = [arr[n], arr[i]];
    }
}

4. Code Explanation

1. Trigger backtrack
2. Check if n equals the length of arr - 1 so that when arr is 4, it can be pushed into res.
3. Swap arr[i] and arr[n] and repeat the whole process with the 1 increased n. (Swap 0th 0th, 1th, 1th, ... , nth nth, and push)
4. After the arr has been pushed, the arr gets back to the original and increase i by 1.
5. Repeat (Swap n-1th nth and push) (Swap n-2th n-1th, n-2th nth, and push)