46. Permutations - cocoder39/coco39_LC GitHub Wiki

46. Permutations

notes 2024:

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        num_set = set()
        res = []
        self.helper(nums, num_set, [], res)
        return res
    
    def helper(self, nums, num_set, path, res):
        if len(path) == len(nums):
            res.append(path[:])
            return
        
        for num in nums:
            if num not in num_set:
                num_set.add(num)
                path.append(num)
                self.helper(nums, num_set, path, res)
                path.pop()
                num_set.remove(num)

Notes 2020:

Solution 1 (Preferred since same approach can be applied to PermutationsII)

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        counters = collections.Counter(nums)
        self.backtrack(counters, len(nums), [], res)
        return res
    
    def backtrack(self, counters, k, path, res):
        if len(path) == k:
            res.append(path[:])
            return
        
        for num in counters:
            if counters[num] > 0:
                path.append(num)
                counters[num] -= 1
                self.backtrack(counters, k, path, res)
                path.pop()
                counters[num] += 1

Solution 2

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        self.backtrack(nums, 0, res)
        return res
    
    def backtrack(self, nums, start, res):
        if start == len(nums):
            res.append(nums[:])
            return
        
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]
            self.backtrack(nums, start+1, res)
            nums[start], nums[i] = nums[i], nums[start]

Time complexity: There are N! solutions in res. For each element in in each solution, there are 3 operations (i.e., 2 swaps and 1 copy). The total time complexity is O(N * N!)

======================================================================================================

permutation of [1, 2, 3] are
[1] + permutation of [2, 3]
[2] + permutation of [1, 3]
[3] + permutation of [1, 2]


permutation of [2, 3] are
[2] + [3]
[3] + [2]

t(n) = n * t(n - 1) = n * (n - 1) * t(n - 2) ... = O(n!)

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        helper(res, nums, 0);
        return res;
    }
private:
    void helper(vector<vector<int>>& res, vector<int>& nums, int start) {
        if (start == nums.size()) {
            res.push_back(nums);
            return;
        }
        
        for (int i = start; i < nums.size(); i++) {
            swap(nums[i], nums[start]);
            helper(res, nums, start + 1);
            swap(nums[i], nums[start]);
        }
    }
};

t(n) = O(n) + n * t(n - 1)
t(n - 1) = O(n) + (n - 1) * t(n - 2)
t(n) = O(n! + n ^ 2) = O(n!)

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> cur;
        vector<bool> visited(nums.size());
        helper(res, cur, visited, nums);
        return res;
    }

    void helper(vector<vector<int>>& res, vector<int>& cur, vector<bool>& visited, vector<int>& nums) {
        if (cur.size() == nums.size()) {
            res.push_back(cur);
            return;
        }
        
        for (int i = 0; i < nums.size(); i++) {
            if (! visited[i]) {
                visited[i] = true;
                cur.push_back(nums[i]);
                helper(res, cur, visited, nums);
                cur.pop_back();
                visited[i] = false;
            }
        }
    }
};
⚠️ **GitHub.com Fallback** ⚠️