Permutations, Subsets and Combinations

result = []
def backtrack(path, option_list):
    # base case
    if satisify the output formaT:
        result.add(path)
        return
    
    for option in option_list:
        make a decision
        backtrack(path, option_list)
        withdraw the decision

class Solution {
public:
    void backtrack(vector<int>& nums, vector<int>& path, vector<vector<int>>& res, vector<int>& visited) {
        if (path.size() == nums.size()) {
            res.push_back(path);
            return;
        }

        // No need to exclude used numbers, but need to exclude invalid combinations
        for (int i = 0; i < nums.size(); i++) {
            if (visited[i] == 1) continue;

            // make a decision
            path.push_back(nums[i]);
            visited[i] = 1;
            
            backtrack(nums, path, res, visited);
			
            // withdraw the decision
            visited[i] = 0;
            path.pop_back();
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> path;
        vector<int> visited(nums.size(), 0);
        backtrack(nums, path, res, visited);
        return res;
    }
};

class Solution {
public:
    void backtrack(int start, const int k, const int n, vector<int>& path, vector<vector<int>>& res) {
        if (path.size() == k) {
            res.push_back(path);
            return;
        }
        // Each cycle starts with "start" to exclude selected numbers
        for (int i = start; i <= n; i++) {
            // make a decision
            path.push_back(i);
            
            backtrack(i + 1, k, n, path, res);
            
            // withdraw the decision
            path.pop_back();
        }
    }

    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        if (n <= 0 || k <= 0) {
            return res;
        }
        vector<int> path;
        backtrack(1, k, n, path, res);
        return res;
    }
};

class Solution {
public:
    void backtrack(int start, vector<int>& nums, vector<int>& path, vector<vector<int>>& res) {
        res.push_back(path);
        
        // Each cycle starts with "start" to exclude used numbers
        for (int i = start; i < nums.size(); i++) {
            // make a decision
            path.push_back(nums[i]);

            // backtracking
            backtrack(i + 1, nums, path, res);

            // withdraw the decision
            path.pop_back();
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> path;
        backtrack(0, nums, path, res);
        return res;
    }
};