Leetcode — combinations/permutations/subsets

Backtracing problems

46 Permutations I

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Solution

class Solution {
public:
    void permute(vector<vector<int>>& answer, vector<int> nums, int begin) {
        if (begin == nums.size()) {
            answer.push_back(nums);
            return;
        }

        for (int i=begin; i<nums.size(); i++) {
            swap(nums[begin], nums[i]);
            permute(answer, nums, begin+1);
            swap(nums[begin], nums[i]);
        } 
    }
    
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> answer;
        permute(answer, nums, 0);
        return answer;
    }
};

47. Permutations II

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Example 1:

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]

Example 2:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

solution

class Solution {
public:
    
    void permute(vector<vector<int>>& ret, vector<int> nums, int next) {
        if (next == nums.size()) {
            ret.push_back(nums);
            return;
        }
        
        for (int i=next; i<nums.size(); i++) {
            if (i != next && nums[next] == nums[i])
                continue;
            swap(nums[i], nums[next]);
            permute(ret, nums, next+1);
        }
        
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        permute(ret, nums, 0);
        return ret;
    }
};

Subset

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
class Solution {
public:
    vector<int> sub;
    vector<vector<int>> subs;
    
    void bt(vector<int>& nums, int next) {
        subs.push_back(sub);
        for (int i=next; i<nums.size(); i++) {
            sub.push_back(nums[i]);
            bt(nums, i+1);
            sub.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        bt(nums, 0);
        return subs;
    }
};

Subset II(with duplicate numbers)

Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
class Solution {
public:
    vector<vector<int>> subs;   
    vector<int> sub;
    
    void bt(vector<int>& nums, int next) {
        subs.push_back(sub);
        for (int i=next; i<nums.size(); i++) {
            if (i != next && nums[i] == nums[i-1]) 
                continue;
            sub.push_back(nums[i]);
            bt(nums, i+1);
            sub.pop_back();
        }
    }
    
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        bt(nums, 0);
        return subs;
    }
};

17. Letter Combinations of a Phone Number

Example 1: implicit backtracing → use stack

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
class Solution {
public:
    vector<vector<char>> pads { {'a', 'b', 'c'}, 
                                {'d', 'e', 'f'},
                                {'g', 'h', 'i'},
                                {'j', 'k', 'l'},
                                {'m', 'n', 'o'},
                                {'p', 'q', 'r', 's'},
                                {'t', 'u', 'v'},
                                {'w', 'x', 'y', 'z'} };
    vector<string> ret;                          
    void bt(int pos, string in, string out) {
        if (pos >= in.size()) {
            ret.push_back(out);
            return;
        }
        
        int digit = in[pos] - '2'; // pads start from 2     
        for (auto c :  pads[digit]) {
            bt(pos + 1, in, out + c); // implicit backtracing
        }
    }
    
    vector<string> letterCombinations(string digits) {
        if (!digits.size())
            return vector<string>();
        
        bt(0, digits, "");
        return ret;
    }
};

solution 2: explicit back tracing → using reference to string “string& combi”

class Solution {
public:
    vector<vector<char>> pads = {
            {'a', 'b', 'c'}, 
            {'d', 'e', 'f'},
            {'g', 'h', 'i'},
            {'j', 'k', 'l'},
            {'m', 'n', 'o'},
            {'p', 'q', 'r', 's'},
            {'t', 'u', 'v'},
            {'w', 'x', 'y', 'z'}
    };
    
    void dfs(vector<string>& answer, string& digits, string& combi, int pos) {
        if (pos == digits.length()) {
            answer.push_back(combi);
            return;
        }
        
        int index = digits[pos] - '2';
        for (auto& c: pads[index]) {
            combi.push_back(c);
            dfs(answer, digits, combi, pos+1);
            combi.pop_back(); // explicit backtracing
        }
    }
    
    vector<string> letterCombinations(string digits) {
        vector<string> answer;
        if (digits == "") {
            return answer;
        }
        string combi;
        dfs(answer, digits, combi, 0);
        return answer;
    }
};

class Solution {
public:
    string comb;
    vector<string> result;
    vector<vector<char>> pads { {'a', 'b', 'c'}, 
                                {'d', 'e', 'f'},
                                {'g', 'h', 'i'},
                                {'j', 'k', 'l'},
                                {'m', 'n', 'o'},
                                {'p', 'q', 'r', 's'},
                                {'t', 'u', 'v'},
                                {'w', 'x', 'y', 'z'} };

    void bt(string digits, string comb, int start) {
        if (start == digits.length()) {
            result.push_back(comb);
            return;
        }
        int num = digits[start] - '2';
        for (int i=0; i<pads[num].size(); i++) {
            comb.push_back(pads[num][i]);
            cout << comb << endl;
            bt(digits, comb, start+1);
            comb.pop_back();
        }
    }

    vector<string> letterCombinations(string digits) {
        if (digits.length())
            bt(digits, comb, 0);
        return result;
    }
};

39. combination sum

class Solution {
public:
    vector<vector<int>> ret;
    void bt(vector<int>& candidates, int next, vector<int> nums, int target) {
        if (target == 0) {
            ret.push_back(nums);
            return;
        } else if (target < 0) {
            return;
        }
        
        for (int i=next; i<candidates.size(); i++) {
            nums.push_back(candidates[i]);
            bt(candidates, i, nums, target - candidates[i]);
            nums.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> nums;
        bt(candidates, 0, nums, target);
        return ret;
    }
};

40. Combination sum II

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output: 
[
[1,2,2],
[5]
]

solution

class Solution {
public:
    
    vector<vector<int>> ans;
    
    void bt(vector<int>& candidates, int next, vector<int> nums, int target) {
        if (target == 0) {
            ans.push_back(nums);
            return;
        } else if (target < 0) {
            return;
        }
        
        for (int i=next; i<candidates.size(); i++) {
            if (i>next && candidates[i] == candidates[i-1])
                continue;
            nums.push_back(candidates[i]);
            bt(candidates, i+1, nums, target - candidates[i]);
            nums.pop_back();
        }
    }
    
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        bt(candidates, 0, vector<int>(), target);
        return ans;
    }
};