题意:给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。
对于给定的输入,保证和为 target 的不同组合数少于 150 个。
解法:
1.审题可知,其实就是回溯算法的应用
2.排列组合的回溯算法实现
3.涉及到重复元素,所以先给数组排序
4.涉及到剪枝,我们由3已知,数组为有序数组,所以遍历过的数字不再遍历,所以记录每次遍历的start位置,用于剪枝
##解法1
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
List<Integer> temp = new ArrayList<Integer>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
backSearch(0, 0, candidates, target);
return ans;
}
private void backSearch(int cur, int start, int[] nums, int target) {
if (cur == target) {
ans.add(new ArrayList<Integer>(temp));
return;
}
if (cur > target) {
return;
}
for (int i = start; i < nums.length; i++) {
temp.add(nums[i]);
cur += nums[i];
backSearch(cur, i, nums, target);
temp.remove(temp.size() - 1);
cur -= nums[i];
}
}
}
网友评论