Generate Combinations
tags: includeexclude backtracking combination prunerecursiontree boundingfunction narrowingthedomainsofthevariables
Given two integers n and k, return all possible combinations of k numbers out of 1 … n. You may return the answer in any order.
Example 1:
Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
Example 2:
Input: n = 1, k = 1
Output: [[1]]
Constraints
 1 <= n <= 20
 1 <= k <= n
Thinking Process
 Define term. Combination A combination is a mathematical technique that determines the number of possible arrangements in a collection of items where the order of the selection does not matter. In combinations, you can select the items in any order.  Order does not matter  Membership
Permutation: [1,2,3] [2,1,3] Combination: [2,1,3]
[1,2] [1,3] [1,4]
[2,3] [2,4]
[3,4]
Do you see any relationship between the input and output? n choose k formula
What can you notice from the output? How the numbers you choose vary from 1 to 4 at the first level? Second level, the numbers vary from 2 to 4. One possible combination.
The value of k is the invariant.
Base Case When do we have one of the possible combinations? When the partial size is the same the value of k, we will add the combination to the output.
Recursive Case How many recursive calls do we need to make? How many subproblems do we have ?
 One subproblem
Iterate through the 1 to n start index .. n
 1 to 4
 2 to 4
 3 to 4
Unit of Work What is the smallest slice of work that I need to in every recursive call? Task: Generate one of the combination. What should I append to the partial? append the index to the partial
How does the parent control the start index for the child? The child will get a new start index.
When to perform the unit of work? Before or After? Look at the diagram to decide whether you need to perform the unit of work before or after.
Time and Space Complexity
Time: O() Space: O()
Implementation


Alternate Implementation


Include Exclude


Key Takeaways
 Expressing the choices at the first level is 1..n
 The number of choices you make reduces as you go down the recursion tree
 We can use the invariant and avoid unnecessary calls by using a bounding function
 Bounding function will prune the recursion tree