🌱 Keegan's Digital Garden

46. Permutations

2 min read

📝 Problem Details

given input array nums (containing distinct integers) return all possible permutations

💭What Were My Initial Thoughts?

- enumeration problem: searching for all possible permutations of a given list of integers
- unlike a subset or powerset, each permutation will be the same size and contain each element once

- backtracking problem
	- choice: picking *which* element to add next
		- since we must use every number exactly once, at each step, we pick one number that hasn't been used yet 
		- this means we probably need a visited set or boolean array to track which numbers are already part of the current permutation
- base case of dfs: if the permutation being constructed matches the size of the original nums vector

💡 Explanation of Solution

1. iterate through all elements and try adding one if its not already used
2. marked it as used, recursively call DFS, then undo the choice (backtrack)
3. once a full permutation is built, store it in result

⌛ Complexity Analysis

Time Complexity: O(2^n)
Space Complexity: O(2^n)

💻 Implementation of Solution

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> curr;
        unordered_set<int> visited;
        dfs(nums, visited, curr, result);
        return result;
    }
 
    void dfs(vector<int>& nums, unordered_set<int>& visited, vector<int>& curr, vector<vector<int>>& result) {
 
        if(curr.size() == nums.size()) {
            result.push_back(curr);
            return;
        }
 
        // explore
        for(int num : nums) {
            if(visited.count(num)) continue; // skip if already used
 
            // choose
            visited.insert(num);
            curr.push_back(num);
 
            // recurse
            dfs(nums, visited, curr, result);
 
            // backtrack
            visited.erase(num);
            curr.pop_back();
        }
 
    }
};

Graph View