Leetcode @ Subsets, Permutations, Combination Sum, Coin Change 题目总结

Subsets, Permutations, Combinations 此类题目都类似，都可以用recursion, backtracking来解，时间复杂度都很高，因为需要in depth search

leetcode上的总结

Let us first review the problems of Permutations / Combinations / Subsets, since they are quite similar to each other and there are some common strategies to solve them.

First, their solution space is often quite large:

• Permutations: $N!$.
• Combinations: $C_N^k = \frac{N!}{(N - k)! k!}$
• Subsets: $2^N$, since each element could be absent or present.

Given their exponential solution space, it is tricky to ensure that the generated solutions are complete and non-redundant. It is essential to have a clear and easy-to-reason strategy.

There are generally three strategies to do it:

• Recursion
• Backtracking
• Lexicographic generation based on the mapping between binary bitmasks and the corresponding
  permutations / combinations / subsets.

As one would see later, the third method could be a good candidate for the interview because it simplifies the problem to the generation of binary numbers, therefore it is easy to implement and verify that no solution is missing.

Besides, this method has the best time complexity, and as a bonus, it generates lexicographically sorted output for the sorted inputs.

下面是具体的题目：

Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

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

Accepted

485,557

Submissions

838,363

BackTracking

class Solution {

public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> cur;
        res.push_back(cur);
        
        for (int &n : nums)
        {
            vector<vector<int>> cur;
            for (auto r : res)
            {
                r.push_back(n);
                cur.push_back(r);
            }
            for (auto c : cur)
            {
                res.push_back(c);
            }
        }
        return res;
    }
};

1. Combination Sum ：没有重复的数组，找出所有unique combinations，数字可以重复利用。

注意这里不需要sort，因为数字无重复。因为数字可以给重复利用，所以 i = index, 也就是自己可以继续add to sum，进入recursion，直到等于或者超过target，再退回来，去加下一个number，所以recursion的退出条件，sum == target, sum > target都很必要。

class Solution {
    void helper(vector<int>& candidates, int target, vector<vector<int>> &res, vector<int> &cur, int index, int sum)
    {
        if (sum == target)
        {
            res.push_back(cur);
            return;
        }
        
        if (sum > target) return;
        
        for (int i = index; i < candidates.size(); i++)
        {
            cur.push_back(candidates[i]);
            helper(candidates, target, res, cur, i, sum + candidates[i]);
            cur.pop_back();
        }
        return;
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> cur;
        helper(candidates, target, res, cur, 0, 0);
        return res;
    }
};

2. Combination Sum II: 和combination sum有很大的不同，首先数组里面有重复数字，但数字不可重复利用，同时返回的结果要是unique的。因为有重复数字，那么就可能有重复结果，只是顺序变了。如何处理？

这个地方破题的关键点在于，如果有多个重复的数字，产生单个结果时我可以用上它们，但是呢，在用它们来产生全局结果时，很可能产生duplicate的结果。

此时，我们可以先sort数组，然后用一个判断条件 if (i > index && candiates[i] == candidates[i-1]) continue; 这句是关键。i > index,  只可能发生在i == index 的recursion已经执行完了，for循环第二层开始了，如果此时当前元素和前一个元素相等, 需要跳过，因为，前面那个同样值的candidate已经产生了所有的含有candidate的结果，不需要再来一遍了。

由于值不能重复利用，在下一个recursion时，要i + 1. 如果可以重复利用，就直接 i 就行了。

class Solution {
    void helper(vector<int>& candidates, int target, vector<vector<int>> &res, vector<int> &cur, int index, int sum)
    {
        if (sum == target)
        {
            res.push_back(cur);   
            return;
        }
        
        if (sum > target) return;
        
        for (int i = index; i < candidates.size(); i++)
        {
            if (i > index && candidates[i] == candidates[i-1]) continue;
            cur.push_back(candidates[i]);
            helper(candidates, target, res, cur, i+1, sum + candidates[i]);
            cur.pop_back();
        }
        return;
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> cur;
        sort(candidates.begin(), candidates.end());
        helper(candidates, target, res, cur, 0, 0);
        return res;
    }
};

3. Combination Sum III: given k numbers that add up to number n, numbers from 1 to 9 can be used. Each combination should be an unique set. 

熟练掌握了I,II后，III就很简单了。相当于{1...9} 的数组，数字不能重复这样的case，只是加了一个限定条件就是结果的size。

class Solution {
    void helper(vector<int> cand, vector<vector<int>> &res, vector<int> &cur, int k, int n, int index, int sum)
    {
        if (cur.size() == k && sum == n)
        {
            res.push_back(cur);
            return;
        }
        
        if (cur.size() > k || sum > n) return;
        
        for (int i = index; i<cand.size(); i++)
        {
            cur.push_back(cand[i]);
            helper(cand, res, cur, k, n, i+1, sum + cand[i]);
            cur.pop_back();    
        }
    }
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> cand;
        for (int i = 1; i<=9; i++)
        {
            cand.push_back(i);
        }
        vector<vector<int>> res;
        vector<int> cur;
        helper(cand, res, cur, k, n, 0, 0);
        return res;
    }
};

4. Combination IV: 给一个正数没有重复数的数组，找出所有可能的combinations的和是一个给定正数，数字可以重复使用, 和I不同的是，这里的order matters, 也就说两个结果，数字相同，但是顺序不同，也算不同的结果，更像permutation sum instead of combination sum。以及这里只需要返回possible number of result就行。follow up: 如果数组里面有负数呢？

这里用的是DP而非recursion。得想想这里怎么做的。

class Solution {
public:
    int combinationSum4(vector<int>& candidates, int target) {
        vector<int> dp(target + 1);
        dp[0] = 1;
        sort (candidates.begin(), candidates.end());
        for (int i = 1; i <= target; i++) {
            for (auto num : candidates) {
                if (i < num) break;
                dp[i] += dp[i - num];
            }
        }
        return dp.back();
    }
};

有人的总结 https://leetcode.com/problems/combination-sum-iv/discuss/85120/C%2B%2B-template-for-ALL-Combination-Problem-Set

5. Coin Change

给一堆硬币，和一个值，找到最少硬币 == 值的硬币个数。看上去和combination sum有点类似，brute force 可以把所有 combination sum都找出来，然后个数最少的返回，不过会超时。既然有最少，那么一看就是DP的感觉，所以看哪些是可重复的计算值，并且思考推导公式。

举例， f(1) = 1, f(2) = 1, f(5) = 1. f(amount) = min(f(amount - coins[i])) + 1
再想想code咋写。得到了推导式，但是怎么一步一步得到f(amount)呢？这里我卡住了。

这里的思路是，针对每一个value, 按照value - coin 的思路循环一次，计算所有已经有最小值的dp[i - coin]。要满足条件就是， i - coin >= 0, dp[i - coin] != -1, dp[i - coin ] < min.

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount == 0) return 0;
        int dp [amount+1] = {-1};
        dp[0] = 0;
        for (int i = 0; i<coins.size() && coins[i] <= amount; i++)
        {
            dp[coins[i]] = 1;
        }
        for (int i = 1; i<=amount; i++)
        {
            int min = INT_MAX;
            for (int &coin : coins)
            {
                if (i - coin >= 0 && dp[i-coin] != -1 && min > dp[i-coin])
                {
                    min = dp[i-coin] + 1;
                }
            }
            dp[i] = min != INT_MAX? min : -1;
        }
        return dp[amount];
    }
};

6. Letter Combinations of a phone number
电话号码排列组合，不难，先把相应数字对应的string给弄出来。再搞两个for loop搞定，反正顺序是一定的。

class Solution {
    void helper(vector<string> cand, vector<string> &res, string &cur, int index)
    {
        if (cand.empty() || cur.size() > cand.size()) return;
        
        if (cur.size() == cand.size())
        {
            res.push_back(cur);
            return;
        }
        for (int i = index; i<cand.size(); i++)
        {
            for (int j = 0; j<cand[i].size(); j++)
            {
                cur.push_back(cand[i][j]);
                helper(cand, res, cur, i+1);
                cur.pop_back();
            }
        }
    }
public:
    vector<string> letterCombinations(string digits) {
        string rec [] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        vector<string> cand;
        for (auto &c : digits)
        {
            cand.push_back(rec[c-'0'-2]);
        }
        vector<string> res;

        string cur;
        helper(cand, res, cur, 0);
        return res;
    }
};