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;
    }
};

Leetcode @ Max job profit in job scheduling

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You're given the startTime , endTime and profit arrays, you need to output the maximum profit you can take such that there are no 2 jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X.

Example 1:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Explanation: The subset chosen is the first and fourth job. 
Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

Example 2:

Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150
Explanation: The subset chosen is the first, fourth and fifth job. 
Profit obtained 150 = 20 + 70 + 60.

Example 3:

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output: 6

Constraints:

• 1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
• 1 <= startTime[i] < endTime[i] <= 10^9
• 1 <= profit[i] <= 10^4

看到这道题感觉自觉会想到dp，贪心算法和 backtracking，它们之间有什么不同以及适合解决什么样的问题？可以总结一下。

问题1. startTime, endTime 是sorted么？如果不是的话，很可能我们需要先建一个data structure再自行sort. 

关键点：对于每一个开始时间，我们可以用map<int, int> dp来存放，map和unordered_map的差别是，map类似于BST，里面的数字是按照key升序排列，搜索是binary search O(logn)，插入一个节点rebalance也是O(logn),记得要初始化map[0] = 0，这是用来方便push in第一个初始工作的。

class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
      int size = profit.size();
      vector<vector<int>> jobs;
      for (int i = 0; i<size; i++)
      {
          jobs.push_back({endTime[i], startTime[i], profit[i]});
      }
      sort(jobs.begin(), jobs.end());
      map<int, int> dp;
      dp.insert({0, 0});
      for (auto &job : jobs)
      {
          auto it = dp.upper_bound(job[1]);
          int cur = job[2] + prev(it)->second;
          if (cur > dp.rbegin()->second)
          {
              dp[job[0]] = cur;
          }
      }
        return dp.rbegin()->second;
    }
};

Trapping Rain Water @ Airbnb

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]

Output: 6

题目分析：

这道题乍一看觉得情况太多，如何遍历？破题的关键点在于，我们只focus在计算一格的容水量的情况。

DP解法：

那么每一格trap water的量由什么决定？由这一格 max (height[0]...height[i]) 和 max(height[i+1], ... height[n]) 最小值决定，同时，这一格本身的高度也不能忽视，假如这一格本身的高度远远高于左右两边的最大值，那么这一格就什么水都容不下，所以在计算最高的时候，把本身也得考虑在那。

推导公式：water can trap = min(max(LMax[0..i]), max(i...n)) - height[i]

此时，可以用DP的方式，扫数组两遍，建立起LMax, RMax, 再最后计算出水容量。

DP的本质就是用空间来置换时间，把可重复利用的中间值保存下来，用来计算最后结果。

Time: O(n), Space: O(n)

class Solution {
    int size;
public:
    int trap(vector<int>& height) {
        // LMax, RMax vector
        size = height.size();
        if (size <= 2) return 0;
        vector<int> LMax(size, 0), RMax(size, 0);
        LMax[0] = height[0];
        RMax[size-1] = height[size-1];
        for (int i = 1; i<size; i++)
        {
            LMax[i] = max(LMax[i-1], height[i]);
        }
        for (int i = size-2; i>=0; i--)
        {
            RMax[i] = max(RMax[i+1], height[i]);
        }
        int res = 0;
        for (int i = 1; i<size; i++)
        {
            res += min(LMax[i], RMax[i]) - height[i];
        }
        return res;
    }
};

2 Pointers:

这个想法很有趣，很巧妙，破题的关键点在于，任何一个格子，和DP解法一样，由左边和右边的最大值来决定，而且不论这个最大值的坐标在哪里，这样我们可以一边动态地找最大值，一边来计算water being trapped amount. 

pointer left = 0, right = n-1, 比较height[left] and height[right],  哪边高度小，哪边先挪动，因为小的那个可以当前确定蓄水量。

关键：当前格子的蓄水量由，min(左边最大，右边最大) - 当前节点高度 决定。

此时假如左边挪动，说明左边指针暂时小于右边，此时遇到新的block的情况只能是两种，小于left，大于left，小于left高度的话，可以蓄水，算出来。大于left高度，不能蓄水。更新指针，往前走，继续比较left 和 right 指针高度。

注意点在于，除了使用left, right指针，还得用两个值lmax, rmax来随时更新当前lmax and rmax的情况。因为蓄水量是等于 lmax - height[left] 和 rmax - height[right] 来决定的。

time: O(n)  space: O(1)

class Solution {
    int size;
public:
    int trap(vector<int>& height) {
        size = height.size();
        if (size <= 2) return 0;
        int res = 0, left = 0, right = size-1, lmax = height[0], rmax = height[size-1];
        while (left < right)
        {
            if (height[left] <= height[right])
            {
                left++;
                if (lmax > height[left])
                {
                    res += lmax - height[left];
                }
                else
                {
                    lmax = height[left];
                }
            }
            else
            {
                right--;
                if (rmax > height[right])
                {
                    res += rmax - height[right];
                }
                else
                {
                    rmax = height[right];
                }
            }
        }
        return res;
    }
};