39. Combination Sum
給定一個由不同整數組成的數組 candidates 和一個目標整數 target，返回所有候選數字的唯一組合，使得所選數字的和等於目標值 target。你可以按任意順序返回組合。
同一個數字可以從 candidates 中被無限制次數地選擇。如果至少有一個選定數字的頻率不同，則兩個組合是唯一的。
測試用例生成的前提是，對於給定的輸入，總共不會超過 150 個組合的唯一組合。
範例 1：
輸入：candidates = [2,3,6,7], target = 7 輸出：[[2,2,3],[7]] 解釋： 2 和 3 是候選數字，且 2 + 2 + 3 = 7。注意，2 可以被多次使用。 7 是候選數字，且 7 = 7。 這是唯一的兩個組合。
Python
from typing import List
class Solution:
def combinationSum(self, candidates: List[int], target: int) ->
List[List[int]]:
result = []
def backtrack(remaining, start, path):
if remaining == 0:
result.append(list(path))
return
elif remaining < 0:
return
for i in range(start, len(candidates)):
path.append(candidates[i])
backtrack(remaining - candidates[i], i, path)
path.pop()
backtrack(target, 0, [])
return result
16.59MB, 52ms
C++
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> result;
vector<int> combination;
backtrack(candidates, target, 0, combination, result);
return result;
}
private:
void backtrack(vector<int>& candidates, int target, int start, vector<int>&
combination, vector<vector<int>>& result) {
if (target == 0) {
result.push_back(combination);
return;
} else if (target < 0) {
return;
}
for (int i = start; i < candidates.size(); ++i) {
combination.push_back(candidates[i]);
backtrack(candidates, target - candidates[i], i, combination, result);
combination.pop_back();
}
}
};
12.27MB, 0ms
Javascript
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function(candidates, target) {
const result = [];
const backtrack = (remaining, start, path) => {
if (remaining === 0) {
result.push([...path]);
return;
} else if (remaining < 0) {
return;
}
for (let i = start; i < candidates.length; i++) {
path.push(candidates[i]);
backtrack(remaining - candidates[i], i, path);
path.pop();
}
};
backtrack(target, 0, []);
return result;
};
53.19MB, 71ms
