回溯算法 的第二天！
題目鏈接：39. 組合總和
狀態(tài)：不了解回溯算法，所以前幾題都是直接看解析做的窑邦，先體驗(yàn)一下。
本題與昨天的題的區(qū)別在于 本題沒有數(shù)量的要求壕探，可以無限重復(fù)冈钦。限制的條件在于總和。所以樹形結(jié)構(gòu)如下：
組合總和樹形結(jié)構(gòu)圖
遞歸的終止條件很清晰了：sum >= target李请。而在sum等于target的時(shí)候瞧筛，就需要收集結(jié)果了。
單層搜索的邏輯：依然是從startIndex開始导盅，搜索candidates集合较幌，區(qū)別就在于本題元素可重復(fù)選擇，所以i不用加一了白翻。
剪枝優(yōu)化：如果下一層的sum(就是本層的sum+candidates[i])已經(jīng)大于target乍炉，就可以結(jié)束本輪for循環(huán)的遍歷了绢片。剪枝代碼如下：
for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++)
完整代碼如下：
class Solution { // Java
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(candidates); // 先進(jìn)行排序
backtracking(res, new ArrayList<>(), candidates, target, 0, 0);
return res;
}
public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {
// 找到了數(shù)字和為 target 的組合
if (sum == target) {
res.add(new ArrayList<>(path));
return;
}
for (int i = idx; i < candidates.length; i++) {
// 如果 sum + candidates[i] > target 就終止遍歷
if (sum + candidates[i] > target) break;
path.add(candidates[i]);
backtracking(res, path, candidates, target, sum + candidates[i], i);
path.remove(path.size() - 1); // 回溯，移除路徑 path 最后一個(gè)元素
}
}
}
復(fù)雜度分析：
時(shí)間復(fù)雜度：O(k * 2^n). 最壞情況下岛琼，遞歸樹的每個(gè)節(jié)點(diǎn)都會(huì)有兩個(gè)分支（即選擇或不選擇當(dāng)前元素）底循，所以遞歸樹的大小為O(2^n), 其中n是candidate數(shù)組的長度；而每次找到一個(gè)滿足條件的組合時(shí)槐瑞，都需要花費(fèi)O(k)的時(shí)間將其復(fù)制到結(jié)果列表res中熙涤，其中k是組合的平均長度。
空間復(fù)雜度：O(k). 遞歸調(diào)用最大深度為k困檩，臨時(shí)路徑path列表的最大長度也是k灭袁。
