网站建设一二级目录,做个人网站需要多少钱,微信小程序数据库搭建,闵行做网站费用题目描述 给定一个候选人编号的集合 candidates 和一个目标数 target #xff0c;找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意#xff1a;解集不能包含重复的组合。
输入示例
candidates [10,1,2,7,…题目描述 给定一个候选人编号的集合 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意解集不能包含重复的组合。
输入示例
candidates [10,1,2,7,6,1,5], target 8,输出示例
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]解题代码
class Solution {ListListInteger result new ArrayList();DequeInteger path new ArrayDeque();public ListListInteger combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);int n candidates.length;boolean[] used new boolean[n];backtrack(candidates, target, 0, 0, used);return result;}public void backtrack(int[] candidates, int targetSum, int sum, int begin, boolean[] used) {if(sum targetSum) {return;}if(sum targetSum) {result.add(new ArrayListInteger(path));return;}for(int i begin; i candidates.length; i) {if(i 0 candidates[i] candidates[i-1] used[i-1] false) {continue;}path.addLast(candidates[i]);sum candidates[i];used[i] true;backtrack(candidates, targetSum, sum, i1, used);used[i] false;sum - candidates[i];path.removeLast();}}
}
