216. Combination Sum III

public class Solution {
    private void Backtrack(int remain, int k, List<int> comb, int nextStart, List<IList<int>> results) {
        if (remain == 0 && comb.Count == k) {
            results.Add(new List<int>(comb));
            return;
        } else if (remain < 0 || comb.Count == k) {
            return;
        }
        for (int i = nextStart; i < 9; i++) {
            comb.Add(i + 1);
            Backtrack(remain - i - 1, k, comb, i + 1, results);
            comb.RemoveAt(comb.Count - 1);
        }
    }
    public IList<IList<int>> CombinationSum3(int k, int n) {
        var results = new List<IList<int>>();
        var comb = new List<int>();
        Backtrack(n, k, comb, 0, results);
        return results;
    }
}

#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:
    private void Backtrack(int remain, int k, List<int> comb, int nextStart, List<vector<int>> results) {
        if (remain == 0 && comb.size() == k) {
            results.push_back(new List<int>(comb));
            return;
        } else if (remain < 0 || comb.size() == k) {
            return;
        }
        for (int i = nextStart; i < 9; i++) {
            comb.push_back(i + 1);
            Backtrack(remain - i - 1, k, comb, i + 1, results);
            comb.RemoveAt(comb.size() - 1);
        }
    }
    public IList<vector<int>> CombinationSum3(int k, int n) {
        var results = new List<vector<int>>();
        var comb = new List<int>();
        Backtrack(n, k, comb, 0, results);
        return results;
    }
}

class Solution {
    protected void backtrack(
        int remain,
        int k,
        LinkedList<Integer> comb,
        int next_start,
        List<List<Integer>> results
    ) {
        if (remain == 0 && comb.size() == k) {
            results.add(new ArrayList<Integer>(comb));
            return;
        } else if (remain < 0 || comb.size() == k) {
            return;
        }

        for (int i = next_start; i < 9; ++i) {
            comb.add(i + 1);
            this.backtrack(remain - i - 1, k, comb, i + 1, results);
            comb.removeLast();
        }
    }

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        LinkedList<Integer> comb = new LinkedList<Integer>();

        this.backtrack(n, k, comb, 0, results);
        return results;
    }
}

var combinationSum3 = function(k, n) {
    const results = [];
    const comb = [];
    
    const backtrack = (remain, k, comb, nextStart) => {
        if (remain === 0 && comb.length === k) {
            results.push([...comb]);
            return;
        } else if (remain < 0 || comb.length === k) {
            return;
        }

        for (let i = nextStart; i < 9; i++) {
            comb.push(i + 1);
            backtrack(remain - i - 1, k, comb, i + 1);
            comb.pop();
        }
    };

    backtrack(n, k, comb, 0);
    return results;
};

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        results = []

        def backtrack(remain, comb, next_start):
            if remain == 0 and len(comb) == k:
                results.append(list(comb))
                return
            elif remain < 0 or len(comb) == k:
                return

            for i in range(next_start, 9):
                comb.append(i + 1)
                backtrack(remain - i - 1, comb, i + 1)
                comb.pop()

        backtrack(n, [], 0)

        return results

package main

func backtrack(remain int, k int, comb []int, nextStart int, results *[][]int) {
    if remain == 0 && len(comb) == k {
        temp := make([]int, len(comb))
        copy(temp, comb)
        *results = append(*results, temp)
        return
    } else if remain < 0 || len(comb) == k {
        return
    }

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

func combinationSum3(k int, n int) [][]int {
    var results [][]int
    var comb []int
    backtrack(n, k, comb, 0, &results)
    return results
}

Explanation

Algorithm

1️⃣

Инициализация и запуск рекурсивной функции:

Создайте вспомогательную функцию backtrack, которая принимает текущую оставшуюся сумму, размер комбинации k, текущую комбинацию, индекс следующего элемента для добавления и список результатов.

Инициализируйте пустые векторы для хранения текущей комбинации и всех возможных результатов.

Запустите функцию backtrack с начальными значениями: полной суммой n, размером комбинации k, пустой комбинацией, начальным индексом 0 и пустым списком результатов.

2️⃣

Рекурсивная обработка:

В функции backtrack проверьте, если текущая сумма равна нулю и размер комбинации равен k, добавьте копию текущей комбинации в список результатов.

Если текущая сумма меньше нуля или размер комбинации равен k, прекратите текущую ветвь обработки.

Иначе, итерируйтесь по оставшимся кандидатам, начиная с текущего индекса. Для каждого кандидата добавьте его в текущую комбинацию, обновите оставшуюся сумму и вызовите backtrack с обновленными параметрами. После возвращения из рекурсивного вызова удалите последний элемент из комбинации для рассмотрения следующего кандидата.

3️⃣

Возвращение результатов:

По завершении всех рекурсивных вызовов функция combinationSum3 возвращает список всех найденных комбинаций.

😎