Skip to content
Tutorials Center
My learning

Topics

Lesson 64 of 225 ยท Recursion and Backtracking

Subsets, Permutations and Combinations

Generate all subsets, permutations and combinations in Python with backtracking, handle duplicates correctly, compare with itertools and learn the counts 2^n, n!, C(n,k).

Three questions come up again and again: which groups can I pick? (subsets), in how many orders can I arrange these? (permutations), and which groups of exactly k can I pick, ignoring order? (combinations). They are the building blocks of many interview problems and the best practice for the backtracking template.

In this lesson you will generate each one from scratch, learn the exact counts, handle inputs that contain duplicates, and see the matching tools in Python's itertools module.

Counting first

Before generating anything, know how many results to expect. It tells you whether the problem is feasible at all.

Object Meaning Count n = 10
Subsets (power set) any group of items, order ignored 2^n 1,024
Permutations all n items in every order n! 3,628,800
k-permutations k items, order matters n! / (n-k)! 720 for k = 3
Combinations k items, order ignored n! / (k! (n-k)!) 120 for k = 3

The subset count comes from a yes/no decision for each item: 2 x 2 x ... x 2. Permutations choose n items for the first slot, n - 1 for the second, and so on. Since these counts explode, generating them is only practical for small n (subsets up to about 20, permutations up to about 9 or 10).

Subsets

For [1, 2, 3] the subsets are [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]: eight, as predicted by 2^3.

Approach 1: include or exclude

At each position, decide whether to take the item or skip it. The leaves of this decision tree are the subsets.

TEXT
                    index 0
               take 1 /     \ skip 1
                  index 1   index 1
             take 2/ \skip  take 2/ \skip
               ...   ...      ...  ...      -> 8 leaves
Python Subsets: include or exclude

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Approach 2: every node is an answer

A second way: every partial path is already a valid subset. A loop picks the next item from the positions after the last chosen one, which also removes order duplicates ([1,2] but never [2,1]).

Python Subsets: record at every node

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The output order differs ([1], [1, 2], [1, 2, 3] ... follow each other), but it contains the same eight subsets. This start pattern is the template for combinations as well.

Approach 3: bitmasks

Because a subset is a yes/no choice per item, an integer from 0 to 2^n - 1 can encode it: bit j set means "item j is in". This is iterative and short, and it leads to bitmask DP.

Python Subsets with bitmasks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All three approaches take O(n * 2^n) time and, apart from the output, O(n) space (the bitmask version uses O(1) beyond each subset).

Combinations

Combinations of k: choose k items, order does not matter. Use the start pattern, and stop when the path has length k. Add pruning: if there are not enough items left to reach k, stop early.

Python Combinations with pruning

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With n = 4 and k = 2 there are 6 combinations: C(4,2) = 4! / (2! 2!) = 6. The loop bound n - needed + 2 is the pruning: for example, when you still need 2 more numbers from 1..4, starting a pick at 4 is pointless because nothing is left after it.

Permutations

For permutations, order matters and every item is used once. At each step we may pick any item not used yet. A boolean list (or a set) tracks what is used.

TEXT
choose first:   1        2        3
choose second: 2  3     1  3     1  2
choose third:  3  2     3  1     2  1
               123 132  213 231  312 321      -> 3! = 6
Python Permutations with a used list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two things to undo this time: the path and the used flag. The work is O(n * n!) (n! leaves, each copied in O(n), and an O(n) scan per node), with O(n) extra space.

A swap-based variant

Instead of a used list, you can build permutations in place: for position pos, swap each later item into that position, recurse, and swap back. It saves the extra list and is a common interview answer.

Python Permutations by swapping

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The order of the results is different from the used version (the swap order is not lexicographic), but it is the same set of six permutations.

Inputs with duplicate values

What if the input is [1, 1, 2]? The code above treats the two 1s as different items, so it produces duplicate results. For permutations, six outputs collapse to only three distinct ones: [1,1,2], [1,2,1], [2,1,1].

The fix is sort first, then skip equal siblings: inside one loop, do not choose a value that equals the previous value at the same level (when the previous one has been tried already).

Python Unique permutations and subsets

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The rule for subsets is i > start and nums[i] == nums[i-1]: skip a repeated value, but only when it is not the first candidate at this level. That keeps [2, 2] (the second 2 is chosen in a deeper level) while removing the duplicate [2].

The Python way: itertools

You rarely write these by hand in production code. itertools has fast C implementations that yield tuples lazily:

Python itertools equivalents

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

itertools.combinations and permutations generate in the order of the input positions, so equal values at different positions are treated as different (the duplicate problem again). math.comb, math.perm and math.factorial compute the counts without generating anything, which is how you should check feasibility first. For more counting formulas see Combinatorics and Counting.

Choosing the right tool

You need Use
Every group of items subsets (2^n)
Groups of exactly k, order ignored combinations (C(n, k))
Every ordering of all items permutations (n!)
Orderings of k out of n k-permutations
Only the count a formula, not generation
Best group under a constraint often DP, not generation

Common mistakes

  • Appending the live path instead of a copy.
  • Forgetting to reset used[i] when undoing a permutation choice.
  • Using i instead of i + 1 for combinations (reuses an item) or i + 1 for combination sum (forbids reuse when it should be allowed).
  • Duplicates in the input without sorting and skipping.
  • Generating when counting is enough: math.comb(40, 20) is instant; listing them is impossible.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How many subsets does a set of 6 distinct items have?

    Each item is either in or out, so there are 2^6 = 64 subsets (including the empty set and the full set).
  2. 2. How many permutations of 5 distinct items are there?

    5! = 5 x 4 x 3 x 2 x 1 = 120.
  3. 3. In the combinations code, why do we recurse with value + 1?

    Starting each next pick after the current one means every combination is built in increasing order exactly once.
  4. 4. What must you do for permutations of an input with repeated values?

    Without a skip rule, equal values at different positions are treated as different items and produce repeated results.
  5. 5. Which call gives the number of 3-element combinations from 10 items without generating them?

    math.comb(n, k) computes C(n, k), here 120. math.perm(10, 3) counts ordered selections (720).

Summary

  • Subsets: 2^n; permutations: n!; combinations of k: C(n, k). Check the count before generating.
  • All three use the backtracking template (choose, explore, undo); the start index prevents reordering duplicates, and a used list allows any unused item.
  • To handle duplicate values: sort, then skip an item equal to its predecessor at the same level.
  • Always store copies of the path.
  • Use itertools.combinations, permutations, product and math.comb/perm in real code.

Next: N-Queens