39. Combination Sum-白红宇

39. Combination Sum

阅读量：6233 次

发布时间：2019-06-22

本文共 5999 字，大约阅读时间需要 19 分钟。

题目：

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

All numbers (including target) will be positive integers.

Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).

The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7,

A solution set is:

[7]

[2, 2, 3]

链接：

题解：

还是一道DFS + Backtracking题。这次是考察重复元素如何处理。依然使用回溯的template。

Time Complexity - O()， Space Complexity - O()

public class Solution {    public List
     
      
       > combinationSum(int[] candidates, int target) {        List
       
        
         > res = new ArrayList<>();        if(candidates == null || candidates.length == 0)            return res;        Arrays.sort(candidates);        ArrayList
         
           list = new ArrayList<>();        dfs(res, list, candidates, target, 0);        return res;    }        private void dfs(List
          
           
            > res, ArrayList
            
              list, int[] candidates, int target, int pos) { if(target < 0) return; if(target == 0) { res.add(new ArrayList
             
              (list)); return; } for(int i = pos; i < candidates.length; i++) { if(candidates[i] > target) return; if(i > 0 && candidates[i] == candidates[i - 1]) continue; list.add(candidates[i]); dfs(res, list, candidates, target - candidates[i], i); list.remove(list.size() - 1); } }}

二刷：

典型的的dfs + backtracking, 一刷到现在有很长时间了,重新做到这题, 才会补充思考以前的不足. 这遍在想能不能用其他的方法, 比如dp或者是类似双指针之类的, 不过可惜最后还是选了这个熟悉的方法.

这里我们主要要注意的是用来回溯的helper方法如何设计, 在我用的方法里, 需要传入已有的变量有

List<List<Integer>> res，这个是我们的结果变量，只有找到满足条件的combination组合之后才会用到

List<Integer> combination，这个是我们用来进行回溯用到的主buffer，根据dfs的深度增加或者减少元素

int[] candidates，这个是题目给定的数组，我们先对其进行sort，然后从小到大遍历来选择合适的元素。这里由于可以不限量选取元素，所以假如candidates中有 <= 0的数就会stack overflow，所以题目中给定元素全是正整数。

int target，这个是我们的目标值， dfs的时候传入下一层是 target - num

int pos，这个是我们的position参数，因为题目要求必须从小到大排序，并且不能有重复，所以我们用pos函数来控制每层dfs不遍历之前已经跳过或者遍历过的元素

接下来就是复杂度分析。这道题的复杂度分析起来比较复杂....一刷的时候就没有好好思考。

首先我们假设这个数组candidate长为n，在其中有m个元素小于target，假设T(n) = find(target)，那么我们可以根据程序得到以下分析结果:

DFS Level 0: 我们首次调用辅助函数，这一层的count = 1

DFS Level 1: 这时候我们进入了辅助函数的for循环，在for循环里我们有一个pruning，当candidate[i] > target的时候，返回，所以这一层我们只对小于target的元素进行下一层DFS，如我们假设的，结果为m

DFS Level 2: 根据代码，我们上一层有一个target -= num，所以这一层的target其实都不一样。
1. 假设我们对candidate中最小的元素min进行分析，这时候新的target₁ = target - min，此时我们要继续计算在candidate数组中有多少元素小于新的target₁，假设这个数目为m₁，则在这一层我们要对小于target₁的m₁个数组进行下一层的DFS
2. 假如我们考虑其他非min的元素来计算总的复杂度时，这时候两层总共要进行1 + m(m₁ + m₂ + m₃ + ... + m_n)次调用。

由于每一层的target和m都在改变，以我的水平比较难计算出一个漂亮的公式，那么我就想办法简化一下：
1. 这里递归的最大深度是d= target / min，就是最深我们可以到 target / min这么多层DFS
2. Branching factor b = m， m是candidate数组里小于等于target的distinct元素的个数。其实这里多算了，每一层的m都在减少，而且是不规则减少
3. 我们利用DFS公式可以算出这里的Time Complexty = O(m^d)， Space Complexity = O(m)
4. 这只是一个worst case scenario，更精确的计算还需要再花时间。

Java:

Time Complexity - O(m^d), Space Complexity - O(m)， m is distinct elements in candidate[] which candidate[i] <= target， d = target / min element in candidate[]

public class Solution {    public List
     
      
       > combinationSum(int[] candidates, int target) {        List
       
        
         > res = new ArrayList<>();        if (candidates == null || candidates.length == 0) {            return res;        }        Arrays.sort(candidates);        List
         
           comb = new ArrayList<>();        combinationSum(res, comb, candidates, target, 0);        return res;    }        private void combinationSum(List
          
           
            > res, List
            
              comb, int[] candidates, int target, int pos) { if (target < 0) { return; } else if (target == 0) { res.add(new ArrayList<>(comb)); } for (int i = pos; i < candidates.length; i++) { int num = candidates[i]; if (num > target) { return; } comb.add(num); combinationSum(res, comb, candidates, target - num, i); comb.remove(comb.size() - 1); } }}

题外话：

1/22/2016

看了地里一些Amazon的Video题目...感觉现在的new graduate孩子们好幸福，随便刷刷题就可以拿offer了，羡慕。但是在看leetcode的时候也发现有些大牛刷题时间有半年甚至1年。有些题目question提问时间是2014年，但在15年下半年还很活跃。在cnblogs里也看到一些人刷题刷了4遍+的。我也还是先好好刷题把，刷到五遍再出关。现在才刚第二遍开头，吃不到葡萄，不要说葡萄酸。

美东这个周末据说会有很大的暴风雪， winter storm Jonas，降雪量可能有10 - 18 inches，幸好周四提前买了好多吃喝备足了。车子加油，也有好几个加油站都卖空了。希望情况不要太严重。

三刷:

方法跟二刷一样。没有特意分析复杂度。

Java:

public class Solution {    public List
     
      
       > combinationSum(int[] candidates, int target) {        List
       
        
         > res = new ArrayList<>();        if (candidates == null) return res;        Arrays.sort(candidates);        getCombinations(res, new ArrayList<>(), candidates, target, 0);        return res;    }        private void getCombinations(List
         
          
           > res, List
           
             list, int[] nums, int target, int pos) { if (target < 0) return; if (target == 0) { res.add(new ArrayList<>(list)); return; } for (int i = pos; i < nums.length; i++) { if (nums[i] > target) break; // Pruning if (i > pos && nums[i] == nums[i - 1]) continue; // Pruning list.add(nums[i]); getCombinations(res, list, nums, target - nums[i], i); list.remove(list.size() - 1); } }}