Leetcode 组合总和问题
2022/2/5 23:42:33
本文主要是介绍Leetcode 组合总和问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- 39.组合总和
- 40.组合总和Ⅱ
- 组合总和Ⅲ
- 组合总和Ⅳ
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]; } }
这篇关于Leetcode 组合总和问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升