文章目录
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];
}
}