77. Combinations

Medium

$$_nC_r=\frac{n!}{r!(n-r)!}$$

Problem:

Given a total number n, return all combinations of k elements.

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.

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

Solution:

Backtracking

1. Start the next number from the last number in the current list: Instead of always starting from 1, you can start from the next number after the last number in the current list. This way, you avoid generating duplicate combinations.

2. Early stopping: If there are not enough numbers left to reach a total of k numbers, you can stop early. For example, if n = 5, k = 3, and the current list is [4], there's no way to pick 3 numbers, so you can stop.

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

        def dfs(start, cur):
            # If the current list has k numbers, add it to the result
            if len(cur) == k:
                result.append(cur[:])
                return

            # If there are not enough numbers left to reach k, stop
            if len(cur) + (n - start + 1) < k:
                return

            for i in range(start, n+1):
                cur.append(i)
                dfs(i+1, cur)
                cur.pop()

        dfs(1, [])
        return result

Time Limit Exceeded

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = set()
        def dfs(cur):
            if len(cur) == k:
                result.add(tuple(sorted(cur[:])))
                return
            for i in range(1, n+1):
                if i not in cur:
                    cur.append(i)
                    dfs(cur)
                    cur.pop()


        dfs([])
        return list(map(list,result))

itertools Module

Reference: itertools Module

import itertools

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        return list(itertools.combinations(range(1, n+1), k))