_77. Combinations.md

77. Combinations

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 07, 2024

Last updated : July 01, 2024

---

Related Topics : Backtracking

Acceptance Rate : 71.47 %

---

Solutions

• m77 v1 itertools.py
• m77.py

Python

m77 v1 itertools.py

# Most straight forwards method given python avalibility :v
# Also by farrrrrr the most efficient since it's a built-in function
# and shows as such in the runtime percentages

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

m77.py

# Manual version to demonstrate understanding

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

        def helper(n: int, k: int, curr: [], remaining: []) :
            if len(curr) == k :
                self.outputCombos.append(curr.copy())
                return

            if not remaining :
                return

            val = remaining.pop()
            helper(n, k, curr, remaining)
            curr.append(val)
            helper(n, k, curr, remaining)
            curr.pop()
            remaining.append(val)

        helper(n, k, currentList, list(range(1, n + 1)))
        return self.outputCombos