Combination Sum II (M)
題目
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates may only be used once in the combination.
Note:
- All numbers (including
target) will be positive integers. - The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
[1,2,2],
[5]
]
題意
給一串數，找出所有和等于目標值的組合，每個數字只能使用一次，且解集中不許有重復的組合，
思路
與 0039. Combination Sum 方法基本一樣，使用回溯法，只是要求數字只能使用一次且不許有重復組合，所以只要加一行對重復元素的判斷和修改遞回引數即可，
代碼實作
Java
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
// 先排序方便處理
Arrays.sort(candidates);
List<List<Integer>> ans = new ArrayList<>();
solve(candidates, target, 0, 0, new ArrayList<>(), ans);
return ans;
}
private boolean solve(int[] candidates, int target, int index, int sum, List<Integer> list, List<List<Integer>> ans) {
if (sum > target) {
return false;
}
if (sum == target) {
ans.add(new ArrayList<>(list));
return false;
}
for (int i = index; i < candidates.length; i++) {
// 相同數字在同一遞回深度只插入一次，以免出現重復組合的情況
if (i > index && candidates[i] == candidates[i - 1]) {
continue;
}
list.add(candidates[i]);
// 每個數字只使用一次，所以遞回時從下一個元素開始，index=i+1
boolean flag = solve(candidates, target, i + 1, sum + candidates[i], list, ans);
list.remove(list.size() - 1);
// 如果遞回回傳值為false，說明剛剛加入的數已經使整個序列的和達到了最大限值
// 不用再繼續加入更大的值，可以直接跳出，
if (!flag) {
break;
}
}
return true;
}
}
JavaScript
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum2 = function (candidates, target) {
candidates.sort((a, b) => a - b)
let res = []
dfs(candidates, 0, 0, target, [], res)
return res
}
let dfs = function (candidates, index, sum, target, list, res) {
if (sum > target) {
return false
}
if (sum === target) {
res.push([...list])
return false
}
for (let i = index; i < candidates.length; i++) {
if (i > index && candidates[i] === candidates[i - 1]) {
continue
}
list.push(candidates[i])
let flag = dfs(candidates, i + 1, sum + candidates[i], target, list, res)
list.pop()
if (!flag) break
}
return true
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/38878.html
標籤：其他