https://leetcode-cn.com/problems/combination-sum/ 数组，回溯算法

对于这种寻找所有解的题目，我们通常都使用回溯算法来解决。

回溯算法

【39】组合总和：中等 - 图1
这是不含剪枝优化的回溯算法

  1. function combinationSum(candidates: number[], target: number): number[][] {
  2.     const res: number[][] = [];
  3.     const dfs = (target: number, combine: number[], idx: number): void => {
  4.         if (idx === candidates.length) {
  5.             return;
  6.         } 
  7.         if (target === 0) {
  8.             res.push(combine)
  9.             return;
  10.         }
  11.         // 直接跳过
  12.         dfs(target, combine, idx + 1)
  13.         // 选择当前数
  14.         if (target - candidates[idx] >= 0) {
  15.             dfs(target - candidates[idx], [...combine, candidates[idx]], idx)
  16.         }
  17.     }
  19.     dfs(target, [], 0);
  20.     return res;
  21. };

回溯算法 + 剪枝

function combinationSum(candidates: number[], target: number): number[][] {
    candidates.sort()
    const res: number[][] = [];
    const dfs = (target: number, combine: number[], idx: number): void => {
        if (target === 0) {
            res.push(combine)
            return;
        }
        for(let i =idx; i < candidates.length; i++) {
            if (target >= candidates[i]) {
                dfs(target - candidates[i], [...combine, candidates[i]], i)
            }
        }
    }

    dfs(target, [], 0);
    return res;
};