Combination Sum (M)
題目
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:
- All numbers (including
target) will be positive integers. - The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Example 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
題意
給一串數，找出所有和等于目標值的組合，每個數字可以重復使用，
思路
排列組合題很容易想到使用回溯法，但與37. Sudoku Solver不同的是，37只要求在回溯中找到一種符合條件的解即可，而本題需要找到所有符合條件的解，因此這兩種回溯法遞回函式回傳值的含義不同(實際上本題遞回函式可以沒有回傳值，但加上回傳值可以在適當的地方直接跳出回圈，提高演算法的效率)，
回溯法實作：
- 先對陣列排序，方便處理，
- 遞回邊界為 sum >= target，其中當 sum == target 時，需要將該解記錄下來，
- 遞回主體：每次加入的值不小于上一次加入的值(因為是遞增數列所以很容易處理)， 加入后進行遞回，遞回完成后將加入的數去掉，如果遞回回傳值為false，說明剛剛加入的數已經使整個序列的和達到了最大限值，不用再繼續加入更大的值，可以直接跳出，
代碼實作
Java
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> ans = new ArrayList<>();
solve(candidates, target, 0, new ArrayList<>(), ans, 0);
return ans;
}
private boolean solve(int[] candidates, int target, int sum, List<Integer> list, List<List<Integer>> ans, int index) {
if (sum > target) {
return false;
}
if (sum == target) {
ans.add(new ArrayList<>(list));
return false;
}
for (int i = index; i < candidates.length; i++) {
list.add(candidates[i]);
boolean flag = solve(candidates, target, sum + candidates[i], list, ans, i);
list.remove(list.size() - 1);
if (!flag) {
break;
}
}
return true;
}
}
JavaScript
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function (candidates, target) {
let res = []
dfs(candidates, 0, 0, target, [], res)
return res
}
let dfs = function (candidates, index, sum, target, list, res) {
if (index === candidates.length || sum > target) {
return
}
if (sum === target) {
res.push([...list])
return
}
list.push(candidates[index])
dfs(candidates, index, sum + candidates[index], target, list, res)
list.pop()
dfs(candidates, index + 1, sum, target, list, res)
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/38877.html
標籤：其他