0046.md

46. Permutations

Java Solution(s)

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> permute(int[] nums) {
        LinkedList<Integer> track = new LinkedList<>();
        boolean[] used = new boolean[nums.length];
        backtrack(nums, track, used);
        return res;
    }

    public void backtrack(int[] nums, LinkedList<Integer> track, boolean[] used) {
        if (track.size() == nums.length) {
            res.add(new LinkedList(track));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            track.add(nums[i]);
            backtrack(nums, track, used);
            used[i] = false;
            track.removeLast();
        }
    }
}

Python Solutions

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        self.res: list[list[int]] = []
        used: list[bool] = [False] * len(nums)
        track: list[int] = []
        self.backtrack(nums, track, used)
        return self.res

    def backtrack(self, nums: list[int], track: list[int], used: list[bool]) -> None:
        if len(track) == len(nums):
            self.res.append([_ for _ in track])
        for i in range(len(nums)):
            if used[i]:
                continue

            used[i] = True
            track.append(nums[i])
            self.backtrack(nums, track, used)
            used[i] = False
            track.pop()