組合總和Leetcode解決方案

例腳

`candidates = [2,3,6,7], target = 7`
`[[2,2,3],[7]]`

`candidates = [2,3,5], target = 8`
`[[2,2,2,2],[2,3,3],[3,5]]`

推薦碼

組合總和Leetcode解決方案的C ++代碼

```#include <bits/stdc++.h>
using namespace std;

void backtrack(vector<vector<int>> &output, vector<int> &current, vector<int> &candidates, int remain, int start){
if(remain < 0)
return;
else if(remain == 0)output.push_back(current);
else {
for(int i=start;i<candidates.size();i++){
current.push_back(candidates[i]);
backtrack(output, current, candidates, remain - candidates[i], i);
current.pop_back();
}
}
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> output;
vector<int> current;
sort(candidates.begin(), candidates.end());
backtrack(output, current, candidates, target, 0);
return output;
}

int main(){
vector<int> cand = {2, 3, 6, 7};
vector<vector<int>> output = combinationSum(cand, 7)	;
for(auto x: output){
for(auto y: x)
cout<<y<<" ";
cout<<endl;
}
}```
```2 2 3
7```

組合總和Leetcode解決方案的Java代碼

```import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
public static List<List<Integer>> combinationSum(int[] nums, int target) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, target, 0);
return list;
}

private static void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
if(remain < 0) return;
else if(remain == 0) list.add(new ArrayList<>(tempList));
else{
for(int i = start; i < nums.length; i++){
backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
tempList.remove(tempList.size() - 1);
}
}
}

public static void main (String[] args) throws java.lang.Exception
{
int[] nums = {2, 3, 6, 7};
List<List<Integer>> output = combinationSum(nums, 7);
for(List<Integer> x: output){
for(Integer y: x)
System.out.print(y+" ");
System.out.println();
}
}
}```
```2 2 3
7```

複雜度分析

時間複雜度

O（N ^（M / T +1）） 其中N是候選項數，M是所有給定整數中最小的候選項，T是目標值。 因此，時間複雜度是指數級的，這是可以預期的，因為該算法是遞歸的回溯。

空間複雜度

O（T / M）， 其中T是目標值，M是所有其他候選項中的最小值。