77. Combinations

leetcode medium

#array#backtracking#csharp#leetcode#medium

Task

Даны два целых числа n и k. Верните все возможные комбинации из k чисел, выбранных из диапазона [1, n].

Ответ можно вернуть в любом порядке.

Пример:

Input: n = 4, k = 2

Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Explanation: There are 4 choose 2 = 6 total combinations.

Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

C# solution

matched/original

public class Solution {
    private int n;
    private int k;
    public IList<IList<int>> Combine(int n, int k) {
        this.n = n;
        this.k = k;
        List<List<int>> ans = new List<List<int>>();
        Backtrack(new List<int>(), 1, ans);
        return ans.Cast<IList<int>>().ToList();
    }
    public void Backtrack(List<int> curr, int firstNum, List<List<int>> ans) {
        if (curr.Count == k) {
            ans.Add(new List<int>(curr));
            return;
        }
        int need = k - curr.Count;
        int remain = n - firstNum + 1;
        int available = remain - need;
        for (int num = firstNum; num <= firstNum + available; num++) {
            curr.Add(num);
            Backtrack(curr, num + 1, ans);
            curr.RemoveAt(curr.Count - 1);
        }
    }
}

C++ solution

auto-draft, review before submit

#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 int n;
    private int k;
    public IList<vector<int>> Combine(int n, int k) {
        this.n = n;
        this.k = k;
        List<List<int>> ans = new List<List<int>>();
        Backtrack(new List<int>(), 1, ans);
        return ans.Cast<vector<int>>().ToList();
    }
    public void Backtrack(List<int> curr, int firstNum, List<List<int>> ans) {
        if (curr.size() == k) {
            ans.push_back(new List<int>(curr));
            return;
        }
        int need = k - curr.size();
        int remain = n - firstNum + 1;
        int available = remain - need;
        for (int num = firstNum; num <= firstNum + available; num++) {
            curr.push_back(num);
            Backtrack(curr, num + 1, ans);
            curr.RemoveAt(curr.size() - 1);
        }
    }
}

Java solution

matched/original

class Solution {
    private int n;
    private int k;

    public List<List<Integer>> combine(int n, int k) {
        this.n = n;
        this.k = k;
        List<List<Integer>> ans = new ArrayList<>();
        backtrack(new ArrayList<>(), 1, ans);
        return ans;
    }

    public void backtrack(
        List<Integer> curr,
        int firstNum,
        List<List<Integer>> ans
    ) {
        if (curr.size() == k) {
            ans.add(new ArrayList<>(curr));
            return;
        }

        int need = k - curr.size();
        int remain = n - firstNum + 1;
        int available = remain - need;

        for (int num = firstNum; num <= firstNum + available; num++) {
            curr.add(num);
            backtrack(curr, num + 1, ans);
            curr.remove(curr.size() - 1);
        }
    }
}

JavaScript solution

matched/original

var combine = function (n, k) {
    const ans = [];
    const backtrack = (curr, firstNum) => {
        if (curr.length === k) {
            ans.push([...curr]);
            return;
        }
        const need = k - curr.length;
        const remain = n - firstNum + 1;
        const available = remain - need;
        for (let num = firstNum; num <= firstNum + available; num++) {
            curr.push(num);
            backtrack(curr, num + 1);
            curr.pop();
        }
    };
    backtrack([], 1);
    return ans;
};

Python solution

matched/original

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtrack(curr, first_num):
            if len(curr) == k:
                ans.append(curr[:])
                return

            need = k - len(curr)
            remain = n - first_num + 1
            available = remain - need

            for num in range(first_num, first_num + available + 1):
                curr.append(num)
                backtrack(curr, num + 1)
                curr.pop()

        ans = []
        backtrack([], 1)
        return ans

Go solution

matched/original

func combine(n int, k int) [][]int {
    var ans [][]int
    var curr []int
    var backtrack func(int)
    backtrack = func(firstNum int) {
        if len(curr) == k {
            ans = append(ans, append([]int{}, curr...))
            return
        }
        need := k - len(curr)
        remain := n - firstNum + 1
        available := remain - need
        for num := firstNum; num <= firstNum+available; num++ {
            curr = append(curr, num)
            backtrack(num + 1)
            curr = curr[:len(curr)-1]
        }
    }
    backtrack(1)
    return ans
}

Explanation

Algorithm

1️⃣

Инициализировать массив ответов ans и массив для построения комбинаций curr.

2️⃣

Создать функцию обратного вызова backtrack, которая принимает curr в качестве аргумента, а также целое число firstNum:

Если длина curr равна k, добавить копию curr в ans и вернуться.

Вычислить available, количество чисел, которые мы можем рассмотреть в текущем узле.

Итерировать num от firstNum до firstNum + available включительно.

Для каждого num, добавить его в curr, вызвать backtrack(curr, num + 1), а затем удалить num из curr.

3️⃣

Вызвать backtrack с изначально пустым curr и firstNum = 1.

Вернуть ans.

😎