題目連結
思路:
這道題與39題思路一緻,隻是在添加結果的過程中,要做到不重複,那麼需要在回溯的過程中進行剪枝,當出現與之前數相同時,需要跳過這個數不選。
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
if (candidates == null || target < 1) {
return res;
}
// 先給數組排序,友善後續處理
Arrays.sort(candidates);
dfs(candidates, target, 0, new ArrayDeque<Integer>(), res);
return res;
}
/**
* 做減法
* @param candidates
* @param target 需要加到的目标和
* @param index 數組元素目前下标
* @param path 存儲每次選中的元素
* @param ans 最終的結果
*/
private void dfs(int[] candidates, int target, int index, Deque<Integer> path,
List<List<Integer>> res) {
// 當目标值減到0時,說明此時選擇的數字滿足要求
if (target == 0) {
res.add(new ArrayList(path));
return ;
}
for (int i = index; i < candidates.length; i++) {
// 如果之前的剩餘的和減去目前數字小于0,則不符合要求,直接跳出循環
if (target - candidates[i] < 0) {
break;
}
// 如果目前數字跟前一個數字相同,則跳過目前數字,因為前一個數字已經選中了
if (i > index && candidates[i] == candidates[i - 1]) {
continue;
}
path.addLast(candidates[i]);
// 開始嘗試下一個位置的數
dfs(candidates, target - candidates[i], i + 1, path, res);
path.removeLast();
}
}
代碼參考自:https://leetcode-cn.com/problems/combination-sum-ii/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-3/