39.组合总和

题目设定：

给的数组没有重复元素，同一个元素可以无限引用，最后的结果不能重复

树形图如下：

因为没有重复元素，不用考虑去重的问题

元素可以重复使用，所以递归的时候需要从 i 往下，而不是i+1

对一个数组且元素相关，需要startindex

故代码如下：

class Solution {private List<List<Integer>> ans = new ArrayList<List<Integer>>();private LinkedList<Integer> path = new LinkedList<Integer>(); public List<List<Integer>> combinationSum(int[] candidates, int target) {backtrack(candidates,target,0,0);return ans;}public void backtrack(int[] candidates,int target,int sum,int startIndex){if(sum>target) return;if(sum == target){ans.add(new ArrayList<> (path));return;}for(int i = startIndex;i<candidates.length;i++){sum+=candidates[i];path.add(candidates[i]);backtrack(candidates,target,sum,i);sum-=candidates[i];path.removeLast();}}
}

剪枝操作:

只需判断sum+candidates[i]<=target即可

但注意，剪枝需要先排序

剪枝后代码：

class Solution {private List<List<Integer>> ans = new ArrayList<List<Integer>>();private LinkedList<Integer> path = new LinkedList<Integer>(); public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);backtrack(candidates,target,0,0);return ans;}public void backtrack(int[] candidates,int target,int sum,int startIndex){if(sum>target) return;if(sum == target){ans.add(new ArrayList<> (path));return;}for(int i = startIndex;i<candidates.length && sum+candidates[i]<=target;i++){sum+=candidates[i];path.add(candidates[i]);backtrack(candidates,target,sum,i);sum-=candidates[i];path.removeLast();}}
}

40.组合总和Ⅱ

题目设定：

给的集合有重复元素，每个元素只能用一次，最后不能有重复集合

树形图：

注意：
有重复元素，就需要去重
去重方法：创建一个boolean[] used 数组，通过一下代码去重

if(i>0 && candidates[i]==candidates[i-1] && !used[i-1])continue;

只能用一次，递归的时候应该是 i+1 ，而不是 i

剪枝的操作同上

代码如下：

class Solution {private List<List<Integer>> ans = new ArrayList<List<Integer>>();private LinkedList<Integer> path = new LinkedList<Integer>();public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);boolean[] used = new boolean[candidates.length];backtrack(candidates,target,0,0,used);return ans;}public void backtrack(int[] candidates, int target,int startIndex,int sum,boolean[] used){if(sum>target) return;if(sum == target){ans.add(new ArrayList<>(path));return;}for(int i = startIndex;i<candidates.length && sum+candidates[i]<=target;i++){if(i>0 && candidates[i]==candidates[i-1] && !used[i-1])continue;used[i] = true;path.add(candidates[i]);sum += candidates[i];backtrack(candidates,target,i+1,sum,used);sum -= candidates[i];path.removeLast();used[i] = false;}}
}

组合总和Ⅲ

题目设定：
找到n个数 和为k 只能有1-9数组且不能有重复数字

树形图：

没有重复数字，只有1-9，即不用去重

数字只能有一个，递归则为 i+1

即先要找k个数字，再判断其和，如果为target，加入ans，如果不是，两种情况一起return到上一层

class Solution {private List<List<Integer>> ans = new ArrayList<List<Integer>>();private LinkedList<Integer> path = new LinkedList<Integer>();public List<List<Integer>> combinationSum3(int k, int n) {backtrack(k,n,1,0);return ans;}public void backtrack(int k,int n,int startindex,int sum){if(path.size() == k){if(sum == n)ans.add(new ArrayList<>(path));return;}for(int i = startindex;i<=9;i++){sum += i;path.add(i);backtrack(k,n,i+1,sum);path.removeLast();sum -= i;}}
}

组合总和Ⅳ

题目设定：
数组元素没有重复的，元素可以无限使用，但是结果可以重复，顺序不同即可

这题我用回溯，超时了

用动态规划，用爬楼梯的思想

target为要上的楼梯的层数，nums[ ]为一次能上的层数

代码：

class Solution {public int combinationSum4(int[] nums, int target) {int[] dp = new int[target+1];dp[0] = 1;for(int i = 1;i<=target;i++){for(int j = 0;j<nums.length;j++){if(i-nums[j]>=0) dp[i] += dp[i-nums[j]];}}return dp[target];}
}