Generate Combinations

tags: include-exclude backtracking combination prune-recursion-tree bounding-function narrowing-the-domains-of-the-variables

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

1. 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]

2. Do you see any relationship between the input and output? n choose k formula

3. 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.

4. The value of k is the invariant.

5. 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.

6. Recursive Case How many recursive calls do we need to make? How many subproblems do we have ?

   • One subproblem

7. Iterate through the 1 to n start index .. n

   1. 1 to 4
   2. 2 to 4
   3. 3 to 4

8. 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

9. How does the parent control the start index for the child? The child will get a new start index.

10. 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def backtrack(start, combination, n, k, output)
  if combination.size == k
    output << combination.dup
    combination = []
    return
  end
    
  for i in (start..n)
    combination << i
    backtrack(i+1, combination, n, k, output)
    combination.pop        
  end
end

# @param {Integer} n
# @param {Integer} k
# @return {Integer[][]}
def combine(n, k)
  output = []
  combination = []
  backtrack(1, combination, n, k, output)
  output
end

Alternate Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

def backtrack(start, combination, n, k, output)    
  if combination.size == k
    output << combination.dup
    # Return from recursion. Climb the tree
    return
  end

  for i in (start..n)
    # Choose the element for the combination
    if i > n-k+1 and combination.empty?
      break
    end

    combination << i
    backtrack(i+1, combination, n, k, output)

    # Unchoose the element for the combination
    combination.pop
  end
end

# @param {Integer} n
# @param {Integer} k
# @return {Integer[][]}
def combine(n, k)
  output = []
  combination = []
    
  backtrack(1, combination, n, k, output)
  output
end

Include Exclude

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def wrapper(a, k, i, candidate, output)
  if i == k
    output << candidate.dup
    
    return
  end
  
  candidate << a[i]
  wrapper(a, k, i+1, candidate, output)
  candidate.pop
  
  wrapper(a, k, i+1, candidate, output)
end

def combine(n, k)
  index = 0
  candidate = []
  output = []
  a = (1..n).to_a 
  
  wrapper(a, k, index, candidate, output)
  output 
end

p combine(4, 2)

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