Skip to content

Backtracking Combination

Table of Contents

77. Combinations

from itertools import combinations
from typing import List


class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        """Backtracking: O(k * C(n,k)) time, O(k) space.
        Prune by ensuring remaining elements suffice for k.
        """
        res = []

        def bt(start: int, path: List[int]) -> None:
            if len(path) == k:
                res.append(path[:])
                return
            for i in range(start, n - (k - len(path)) + 2):
                path.append(i)
                bt(i + 1, path)
                path.pop()

        bt(1, [])
        return res

    def combineItertools(self, n: int, k: int) -> List[List[int]]:
        """Itertools: O(k * C(n,k)) time, O(k) space.
        Leverage stdlib combinations generator.
        """
        return [list(c) for c in combinations(range(1, n + 1), k)]


def test_combine():
    s = Solution()
    for fn in (s.combine, s.combineItertools):
        assert sorted(fn(4, 2)) == sorted(
            [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
        )
        assert sorted(fn(4, 3)) == sorted([[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]])
        assert fn(1, 1) == [[1]]

216. Combination Sum III

import itertools
from typing import List


# 1. Backtracking
def combinationSum3(k: int, n: int) -> List[List[int]]:
    path, result = [], []

    def backtracking(start):
        if len(path) == k and sum(path) == n:
            result.append(path[:])
            return

        for i in range(start, 10):
            path.append(i)
            backtracking(i + 1)
            path.pop()

    backtracking(1)

    return result


# 2. Itertools
def combinationSum3Itertools(k: int, n: int) -> List[List[int]]:
    combinations = itertools.combinations(range(1, 10), k)
    result = []

    for i in combinations:
        if sum(i) == n:
            result.append(i)

    return result


print(combinationSum3(3, 7))  # [[1, 2, 4]]
print(combinationSum3Itertools(3, 7))  # [(1, 2, 4)]

22. Generate Parentheses

from typing import List


# Backtracking
def generateParenthesis1(n: int) -> List[str]:
    path, res = [], []

    def dfs(openN, closeN):
        if openN == closeN == n:
            res.append("".join(path))
            return

        if openN < n:
            path.append("(")
            dfs(openN + 1, closeN)
            path.pop()

        if closeN < openN:
            path.append(")")
            dfs(openN, closeN + 1)
            path.pop()

    dfs(0, 0)

    return res


# Backtracking
def generateParenthesis2(n: int) -> List[str]:
    m = n * 2
    res, path = [], [""] * m

    def dfs(i, left):
        if i == m:
            res.append("".join(path))
            return

        if left < n:
            path[i] = "("
            dfs(i + 1, left + 1)
        if i - left < left:
            path[i] = ")"
            dfs(i + 1, left)

    dfs(0, 0)
    return res


if __name__ == "__main__":
    print(generateParenthesis1(3))
    # ['((()))', '(()())', '(())()', '()(())', '()()()']
    print(generateParenthesis2(3))
    # ['((()))', '(()())', '(())()', '()(())', '()()()']

301. Remove Invalid Parentheses