Skip to main content

77. Combinations

https://leetcode.com/problems/combinations/

Python​

Backtracking​

A general algorithm for finding solutions to some computational problems.

Wikipedia - Backtracking

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        return self._backtrack(k, n, 1, [], [])

    def _backtrack(self, k: int, n: int, start: int, current: List[int], result: List[List[int]]):

        if len(current) == k:
            result.append(current[:])

        for i in range(start, n+1):
            current.append(i)
            self._backtrack(k, n, i+1, current, result)
            current.pop()

        return result

Python Itertools built-in package​

Cheet with Python...lol

from itertools import combinations

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        return [comb for comb in combinations([num for num in range(1, n+1)], k)]

Javascript​

var combine = function (n, k) {
	const record = [];
	const result = [];

	backtracking(record, 1, n, k, result);

	return result;
};

var backtracking = function (record, start, n, k, result) {
	if (record.length === k) {
		result.push(record.slice(0));
		return;
	}

	for (let i = start; i <= n; i++) {
		record.push(i);
		backtracking(record, i + 1, n, k, result);
		record.pop();
	}
};