【Leetcode】39. Combination Sum

题目：https://leetcode.com/problems/combination-sum/?tab=Description

返回所有不同的和为target的解。

属于返回所有解的题目，一般来讲需要用backtrakcing思路。因此复杂度比较高，这个是指数级别。

返回所有解的问题一个难点在于去重。

（1）因此在函数中要加入一个start参数，使得后续的步骤不会往前看。

（2）如果有重复元素，那么只能第一次使用。也就是需要检测是否和前一个相等，如果相等，看下一个。

public List<List<Integer>> combinationSum(int[] candidates, int target) { //Arrays.sort(candidates); List<List<Integer>> result = new ArrayList<>(); List<Integer> l = new ArrayList<>(); cacu(candidates, target, l, result, 0); return result; } public boolean cacu(int[] candidates, int target, List<Integer> cash, List<List<Integer>> result, int b) { if (target == 0) {result.add(new ArrayList<>(cash)); return true;} if (target < 0) return false; for (int i = b; i < candidates.length; i++) { cash.add(candidates[i]); cacu(candidates, target - candidates[i], cash, result, i); cash.remove(cash.size() - 1); } return false; } 后来发现，有时候backtracking和dp的应用场景分不清，其实dp问题用于解决最优解或者数目问题，即这类问题返回的是一个解。对于这种返回所有解的题目并不是dp做的。当然在某些情况下也是可以的。主要看能否建立一个memo。这个题目我也尝试了dp，发现建立不了memo，放弃了。。。只想出一个子问题方法；

public List<List<Integer>> combinationSum(int[] candidates, int target) { if(candidates == null || candidates.length == 0) return new ArrayList<>(); return combinationSumSub(candidates, target, 0); } public List<List<Integer>> combinationSumSub(int[] candidates, int target, int start) { Map<int[], Integer> a = new HashMap<>(); List<List<Integer>> r = new ArrayList<>(); if(target == 0){ r.add(new ArrayList<>()); return r; } if(start >= candidates.length || target < 0) return r; for(int i = start; i < candidates.length; i++){ List<List<Integer>> sub = combinationSumSub(candidates, target - candidates[i], i); for(List<Integer> list : sub){ list.add(0, candidates[i]); r.add(list); } } return r; }