Combinations

To solve this problem, you can use the concept of recursion or backtracking. You can start by considering each number i from 1 to n, and then recursively finding all combinations of size k-1 from the remaining numbers.

Here is a Python solution using backtracking:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtrack(start, curr):
            # if the combination is done
            if len(curr) == k:  
                output.append(curr[:])
                return
            for i in range(start, n + 1):
                # add i into the current combination
                curr.append(i)
                # use next integers to complete the combination
                backtrack(i + 1, curr)
                # backtrack, remove i from the current combination
                curr.pop()

        output = []
        backtrack(1, [])
        return output

In this code, the backtrack function generates all combinations of size k starting from start. If the current combination curr has size k, it is added to the output list. Otherwise, for each integer i from start to n, i is added to curr, and then backtrack is called recursively to complete the combination. After that, i is removed from curr to try the next combination. The final list of all combinations is returned as the result.

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 combination? 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. 1 to 4
2. 2 to 4
3. 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

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

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 combination? 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. 1 to 4
2. 2 to 4
3. 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

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
You make the

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

title: Combination excerpt: This covers generating combinations with duplicates and without duplicates. tags: using-index-in-base-case

A combination is a subset of a set of objects. For example, in the set {A, B, C}, the subset {A, B} is a combination. All the combinations for the set {A, B, C} are {A, B}, {A, C} and {B, C}. In a combination the ordering of the items in a set does not matter. So {A, B} is considered the same as {B, A}.

It is similar to a menu selection at a restaurant. Selecting a fish sandwich and fries is the same as selecting fries and fish sandwich. If we know how many items to select from a set whe can use nested for loops to generate combinations. However the loops needed will be equal to the number of items taken from the set. Sometimes we do not know how many items we have to select when we write the code. So we cannot write a program that uses an unknown number of for loops.

Combinations with Duplicates

You can solve this problem recursively. Each recursive call is responsible for adding a single combination to the result. Then, if the result does not include enough combinations, recursive calls are made to generate more combinations. When the combination generation is complete, we can print the list of combinations.

 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
def combination_with_duplicates(array, index, combinations, output)
  # Check if we have made the last assignment
  if index == combinations.size
    # Save the result
    result = []
    for i in (0..combinations.size-1)
      result.append(array[combinations[i]])
    end
    output.append(result)
  else
    # Get the smallest value we can use for the next combination
    # Start is used for the first index
    start = 0
    if index > 0
      start = combinations[index - 1]
    end

    # Make the next assignment
    for i in (start..array.size-1)
      # Add item i to the combination
      combinations[index] = i
      
      # Recursively make the other combinations
      combination_with_duplicates(array, index + 1, combinations, output)
    end
  end
end

The index parameter gives the index of the item in the combination that this recursive call to the method should set. If index is 4, this call to the method fills in combinations[4].

The combinations array holds the indices of the items in the combination. For example, if combinations holds two entries and its values are 2 and 4, the combination includes the items with indices 2 and 4. The items array stores the items from which the combinations should be made.

The output is an array of arrays of items representing the complete combinations. For example, if a combination is [A,B,E], output holds an array including the indices of A, B and E.

The method first checks if the index of the item in the combination it should make. If this value is greater than the length of the combinations array, the combination is complete, so it is added to the output array.

If the combination is incomplete, the method determines the smallest index in the array that it could use for the next choice in the combination. If this call is filling in the first position in the selections array, it could use any value in the array, so start is set to 0. If this call does not set the first item in the combination, the method sets start to be the index of the last chosen value.

For example, suppose the items are [A, B, C, D, E] and the method has been called to fill in the third choice. Suppose also that the first two choices were the items with indices 0 and 2, so the current combination is [A, C]. In that case the method sets start to 3, so the items it considers for the next position have indices of 3 or greater. That makes it pick between D and E for this combination.

Setting start in this way keeps the items in the combination in order. In this example, that means the letters in the selection are always in alphabetical order. That prevents the method from picking two combinations such as [A, C, D] and [A, D, C], which are the same items in different order.

The method loops from start to the last index in the input array. For each of those values, the method places the value in the combinations array to add the corresponding item to the combination and then calls itself recursively to assign values to the other entries in the combinations array.

Combinations Without Duplicates

To generate combinations without duplicates, only one small change needs to be made to the previous implementation. Instead of setting the start variable equal to the index last added to the combinations array, set it to 1 greater than that index. This prevents the selection of the same value again.

 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 unique_combination(index, combinations, array, output)
  # Check if we have made the last assignment
  if index == combinations.size
    # save the result in the output array
    for i in (0..combinations.size - 1)
      output.append(array[combinations[i]])
    end
  else
    # Get the smallest value we can use for the next combination
    # 0 index is used for the first index
    start = 0
    if index > 0
      start = combinations[index - 1] + 1
    end
    
    # Make the next assignment
    for i in (start..array.size - 1)
      # Add item i to the combination
      combinations[index] = i
      
      # recursively make the other combinations
      unique_combination(index + 1, combinations, array, output)
    end
  end
end

This method works the same way as before, but this time each choice for an item in the combination must come after the one before it in the input array. For example, suppose the items are [A, B, C, D], the method has already chosen [A, B] for the partial combination and now the method has been called to make the third combination. In that case, the method considers only the items that come after B, which are C and D.