广州做网站mxszpt,图片上传分享平台,兴县网站建设,做网站从哪里找货源题目#xff1a; 给定一个候选人编号的集合 candidates 和一个目标数 target #xff0c;找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次 。 注意#xff1a;解集不能包含重复的组合。
示例 1:
输入: ca…题目 给定一个候选人编号的集合 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次 。 注意解集不能包含重复的组合。
示例 1:
输入: candidates [10,1,2,7,6,1,5], target 8,输出:[[1,1,6],[1,2,5],[1,7],[2,6]]
示例 2:
输入: candidates [2,5,2,1,2], target 5,输出:[[1,2,2],[5]]
解答
思路1
在No39CombinationSum基础上每次回溯从下一个位置开始。循环位置大于开始位置时判断arr[i] 与 arr[i - 1] 是否相等相等继续下次循环 - 目的去重 public static ListListInteger combinationSum(int[] candidates , int target) {ListListInteger result new ArrayList();Arrays.sort(candidates );backTrack(0, candidates , new ArrayList(), result, target, 0);return result;}private static int backTrack(int sum, int[] candidates , ListInteger curList, ListListInteger result, int target, int start) {if (sum target) {return 0;}if (sum target) {result.add(new ArrayList(curList));return 1;} else {for (int i start; i candidates .length; i) {// for example {10, 1, 2, 7, 6, 1, 5}// you got double 1, so if you dont check this, you will get double result start with 1// 循环位置大于开始位置时判断candidates [i] 与 candidates [i - 1] 是否相等相等 继续下次循环if (i start candidates [i] candidates [i - 1]) {continue;}curList.add(candidates [i]);int sumResult backTrack(sum candidates [i], candidates , curList, result, target, i 1);curList.remove(curList.size() - 1);if (sumResult ! -1) {break;}}}return -1;}
