LeetCode【39.组合总数】

您所在的位置：网站首页 › 组合总数和排列总数 › LeetCode【39.组合总数】

LeetCode【39.组合总数】

2023-07-17 07:52| 来源: 网络整理| 查看: 265

leetcode【39.组合总数】

题目描述：

给定一个无重复元素的数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。

示例 1:

输入： candidates = [2,3,6,7],target = 7;所求解集为：

[

[7],

[2,2,3]

]

示例 2:

输入： candidates = [2,3,5],target = 8;所求解集为：

[

[2,2,2,2],

[2,3,3],

[3,5]

]

思路

本题的要点在于可以无限制的使用重复的数字，所以在递归的时候需要再次使用i进行回溯，每次回溯需要将上次加入的元素删除，在递归中每次使用的循环需要从当前的索引开始；target小于0则直接返回；target等于0则直接加入res，（注意：res.add(new ArrayList(list))这个不需重新申请空间，再次赋值给res）。

代码

class Solution { public List combinationSum(int[] candidates, int target) { List res = new ArrayList(); dfs(candidates, target, new ArrayList(), 0, res); return res; } public void dfs(int[] candidates, int target, List list, int index, List res ) { if(target res.add(new ArrayList(list)); return; }else{ for(int i = index; i public List combinationSum(int[] candidates, int target) { List res = new ArrayList(); dfs(candidates, target, 0, new ArrayList(), res); return res; } public void dfs(int[] candidates, int target, int index, List list, List res){ if(target res.add(new ArrayList(list)); return; } for(int i = index; i public static int[] StringToArrays(String input) { input = input.trim(); input = input.substring(1, input.length() - 1); if(input == null) { return new int[0]; } String[] parts = input.split(","); int[] res = new int[parts.length]; for(int i = 0; i if(length == 0) { return "[]"; } String result = ""; for(int i : nums) { result += i; result += ", "; } return "[" + result.substring(0, result.length() - 2 ) +"]"; } public static String integerArrayListToString(List nums) { return integerArrayListToString(nums, nums.size()); } public static String int2dListToString(List nums) { StringBuilder sb = new StringBuilder("["); for(List list : nums) { sb.append(integerArrayListToString(list)); sb.append(","); } sb.setCharAt(sb.length() - 1, ']'); return sb.toString(); } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String line = null; while((line = in.readLine()) != null) { int target = Integer.parseInt(in.readLine()); int[] candidates = StringToArrays(line); List ret = new Solution().combinationSum(candidates, target); String out = int2dListToString(ret); System.out.println(out); //System.out.println(ret.toString()); } } }

【本文地址】

LeetCode【39.组合总数】

LeetCode【39.组合总数】

今日新闻

推荐新闻