39. Combination Sum

public class Solution {
    public IList<IList<int>> CombinationSum(int[] candidates, int target) {
        List<IList<int>> results = new List<IList<int>>();
        this.backtrack(target, new List<int>(), candidates, 0, results);
        return results;
    }
    private void backtrack(int remain, List<int> comb, int[] candidates,
                           int start, List<IList<int>> results) {
        if (remain == 0) {
            results.Add(new List<int>(comb));
            return;
        } else if (remain < 0) {
            return;
        }
        for (int i = start; i < candidates.Length; ++i) {
            comb.Add(candidates[i]);
            this.backtrack(remain - candidates[i], comb, candidates, i,
                           results);
            comb.RemoveAt(comb.Count - 1);
        }
    }
}

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public IList<vector<int>> CombinationSum(vector<int>& candidates, int target) {
        List<vector<int>> results = new List<vector<int>>();
        this.backtrack(target, new List<int>(), candidates, 0, results);
        return results;
    }
    private void backtrack(int remain, List<int> comb, vector<int>& candidates,
                           int start, List<vector<int>> results) {
        if (remain == 0) {
            results.push_back(new List<int>(comb));
            return;
        } else if (remain < 0) {
            return;
        }
        for (int i = start; i < candidates.size(); ++i) {
            comb.push_back(candidates[i]);
            this.backtrack(remain - candidates[i], comb, candidates, i,
                           results);
            comb.RemoveAt(comb.size() - 1);
        }
    }
}

class Solution {
    protected void backtrack(
        int remain,
        LinkedList<Integer> comb,
        int start,
        int[] candidates,
        List<List<Integer>> results
    ) {
        if (remain == 0) {
            results.add(new ArrayList<Integer>(comb));
            return;
        } else if (remain < 0) {
            return;
        }

        for (int i = start; i < candidates.length; ++i) {
            comb.add(candidates[i]);
            this.backtrack(
                    remain - candidates[i],
                    comb,
                    i,
                    candidates,
                    results
                );
            comb.removeLast();
        }
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        LinkedList<Integer> comb = new LinkedList<Integer>();

        this.backtrack(target, comb, 0, candidates, results);
        return results;
    }
}

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    let sols = [];
    let sum_rec = (curr_trial, curr_sum, start_idx) => {
        for (let i = start_idx; i < candidates.length; i++) {
            const c = candidates[i];
            curr_sum += c;
            curr_trial.push(c);
            if (curr_sum < target) {
                sum_rec(curr_trial, curr_sum, i);
            } else if (curr_sum === target) {
                sols.push(JSON.parse(JSON.stringify(curr_trial)));
            }
            curr_sum -= c;
            curr_trial.pop();
        }
    }
    sum_rec([], 0, 0);
    return sols;
};

class Solution:
    def combinationSum(self, candidates, target):
        results = []

        def backtrack(remain, comb, start):
            if remain == 0:
                results.append(list(comb))
                return
            elif remain < 0:
                return

            for i in range(start, len(candidates)):
                comb.append(candidates[i])
                backtrack(remain - candidates[i], comb, i)
                comb.pop()

        backtrack(target, [], 0)

        return results

func combinationSum(candidates []int, target int) [][]int {
    var results [][]int
    var comb []int
    backtrack(target, comb, 0, candidates, &results)
    return results
}

func backtrack(
    remain int,
    comb []int,
    start int,
    candidates []int,
    results *[][]int,
) {
    if remain == 0 {
        newComb := make([]int, len(comb))
        copy(newComb, comb)
        *results = append(*results, newComb)
        return
    } else if remain < 0 {
        return
    }

    for i := start; i < len(candidates); i++ {
        comb = append(comb, candidates[i])
        backtrack(remain-candidates[i], comb, i, candidates, results)
        comb = comb[:len(comb)-1]
    }
}

Algorithm

1️⃣

Как видно, вышеописанный алгоритм обратного отслеживания разворачивается как обход дерева в глубину (DFS - Depth-First Search), который часто реализуется с помощью рекурсии.

Здесь мы определяем рекурсивную функцию backtrack(remain, comb, start) (на Python), которая заполняет комбинации, начиная с текущей комбинации (comb), оставшейся суммы для выполнения (remain) и текущего курсора (start) в списке кандидатов.

Следует отметить, что сигнатура рекурсивной функции немного отличается в Java, но идея остается той же.

2️⃣

Для первого базового случая рекурсивной функции, если remain == 0, то есть мы достигаем желаемой целевой суммы, поэтому мы можем добавить текущую комбинацию в итоговый список.

Как другой базовый случай, если remain < 0, то есть мы превышаем целевое значение, мы прекращаем исследование на этом этапе.

3️⃣

Помимо вышеупомянутых двух базовых случаев, мы затем продолжаем исследовать подсписок кандидатов, начиная с [start ... n].

Для каждого из кандидатов мы вызываем рекурсивную функцию саму с обновленными параметрами.

Конкретно, мы добавляем текущего кандидата в комбинацию.

С добавленным кандидатом у нас теперь меньше суммы для выполнения, то есть remain - candidate.

Для следующего исследования мы все еще начинаем с текущего курсора start.

В конце каждого исследования мы делаем откат, удаляя кандидата из комбинации.

😎