Subsets and permutations in Python

Why it matters

Many interview problems ask you to list every possibility, or to count the ones that meet a rule. Which combinations of items cost exactly 100? Which orders of letters form a valid word? Which groups of numbers add up to a target? These questions are called search problems, and the main tool for them is backtracking. Subsets and permutations are the two templates behind most of them. Once you can write those two templates from memory and explain how they work, you can adapt them to many other problems.

This lesson uses recursion, the base case and the call stack from the first lesson, and the index habit from the second. The new idea is that a recursive function can build an answer one choice at a time and take each choice back when it has finished exploring it.

The idea from the first principle

Start with a plain situation. You are choosing a snack from a list of three: an apple, a biscuit and a cake. You can take none of them, one of them, two of them or all three. How many different snack choices are there? For each item you make a yes or no decision: take it, or leave it. Three items with two answers each give 2 times 2 times 2, which is 8 possible choices. That count is the number of subsets of a list, where a subset is any selection of items, including the empty selection and the full list.

Now the second situation. You are lining up three friends for a photo. The order matters: Ana, Ben, Chloe is different from Chloe, Ben, Ana. The number of different orders is 3 times 2 times 1, which is 6. That count is the number of permutations of a list, where a permutation is an arrangement that uses every item exactly once.

Both counts grow fast. A list of 4 items has 16 subsets and 24 permutations. A list of 10 items has 1,024 subsets and about 3.6 million permutations. Any method that lists them all must do at least that much work, so these problems are expensive by nature. Backtracking does not make them cheap. It makes them correct, complete and easy to check.

The key picture is a decision tree. Each level of the tree is one decision. Each path from the top to a leaf is one complete choice. A subset of three items is a path through three decisions, and a permutation of three items is a path through three decisions where each option is used only once. The tree has as many leaves as there are answers.

Backtracking: choose, explore, undo

Backtracking is recursion that builds an answer one choice at a time. When it has explored one choice completely, it undoes that choice and tries the next one. The name comes from the way a walker in a maze retreats to the last fork and takes another path when a route fails.

The pattern has three steps, and you should say them in order every time you write this kind of function:

1. Choose. Add one option to the answer you are building.
2. Explore. Call the function again to decide the rest.
3. Undo. Remove the option you added, so that the next choice starts from the same state as this one did.

In Python the choose step is usually current.append(item), and the undo step is current.pop(). The append method adds an item to the end of a list, and pop removes the last item and gives it back.

The undo step is the heart of the idea. The same list and the same flags are shared by every branch of the tree. If you forget to undo a choice, later branches start from a polluted state, and you get wrong answers that look plausible. You will see that exact failure in the Common mistakes section, with its real output.

Watch the state as the calls go down and come back up. The list current is the state. On the way down it grows by one item per choice. On the way back up each pop shrinks it again, so the next branch starts from the same list as the one before it.

Subsets: skip or take each item

A subset is built by walking through the items one at a time. At each item you have two choices: skip it, or take it. The base case is reached when every item has been decided. At that moment the current selection is one complete subset, and you save it.

For the list [1, 2, 3], the first decision is about 1. If you skip 1, you then decide about 2 and 3, and if you take 1, you decide the same way with 1 already chosen. The tree has three levels, and it has eight leaves, one for each subset.

Here is the Python code. It uses an index to say which item is being decided, a list called current to hold the choices so far, and a list called result to hold the finished subsets:

Press Run. The output is:

[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
count = 8

Read the code line by line, because it is the template for the rest of this lesson. The first if is the base case. When the index reaches the end of the list, every item has been decided, so the function saves a copy of current. The expression current[:] makes that copy. A slice with no start or end, written [:], returns a new list with the same items. Then the function makes two calls for the current index: one that skips the item, and one that takes it, adds it to current, explores, and removes it again.

Trace the first few steps. The function starts with the index at 0 and an empty current. It skips 1, skips 2 and skips 3, and reaches the base case with an empty selection. That is the first result, []. Back at index 2, it takes 3, reaches the base case, and saves [3]. Back at index 1, the function had skipped 2; now it takes 2, and then at index 2 it saves [2] after skipping 3 and [2, 3] after taking 3. The output order follows the tree from the skip branch down first, which is why [] comes first and [1, 2, 3] comes last.

Notice the copy in current[:]. Without it, every saved entry would point to the same list object. That list is changed as the recursion runs. By the time the function finishes, the list is empty, so every entry would print as []. The next section shows that exact result.

The count of subsets is always 2^n for n items, because each item doubles the number of choices. The time cost is O(2^n * n), since there are 2^n subsets and copying each one takes up to n steps. The stack depth is O(n), since each level of the tree is one call deeper.

The tree for the smaller list [1, 2] has four leaves. Each leaf is one subset, and the path to each leaf is a sequence of skip and take decisions. Written out as text, with s for skip and t for take:

                 start
              /         \
          s (skip 1)   t (take 1)
          /     \       /      \
     s (skip 2) t    s (skip 2) t (take 2)
        []    [2]      [1]       [1, 2]

What happens without the copy

Here is the same function with one change: it saves current itself, not a copy. This shows you what the copy protects against. The program prints the result after the recursion has finished:

Press Run. The output is:

[[], [], [], [], [], [], [], []]

There are eight entries, which is right, but every entry is an empty list. Each entry in result is a reference to the same current list. When the recursion finishes, every append has been undone, so that single list is empty. The fix is one change: save current[:], or list(current). The lesson for the whole module is this. Whenever you save an answer from a backtracking function, you must copy it, because the state you are building keeps changing.

Counting subsets that hit a target

Many questions do not ask for the list of subsets. They ask how many subsets meet a rule. Here the best template is to carry the running total as a parameter, and return a count instead of saving every subset. You do not need to store anything, so the space cost drops to the stack depth alone.

Think of a shop with items priced 1, 2, 3 and 4. A customer wants a bundle that costs exactly 5. The answer is the number of bundles whose prices add to 5. The function decides each item, passing along the total so far, and at the end it checks whether the total matches the target:

The output is:

subsets with sum 5: 2

The two bundles are {1, 4} and {2, 3}. Notice that the function does not use pop. It passes total + nums[i] as a new value into the take call, so the parent's total is never changed. This is a second way to backtrack: pass the state down as a value, so each branch has its own copy and nothing needs to be undone. Both styles are correct. The undo style saves memory when the state is large, and the value style is shorter and harder to get wrong.

Look at the two lines skip = ... and take = .... Each is one branch of the decision tree, and the function adds the two counts. Writing the calls into variables first makes the structure clear. You can write return count(...) + count(...) as well, which is shorter but does the same work.

The time is O(2^n), because the function visits each subset once. The stack depth is O(n). This version is fine for up to about 20 items. For bigger lists you need a smarter method, such as a dynamic programming table over the possible sums, which you will meet in a later module.

Combinations: choose k items in order

A combination is a subset of a fixed size. The difference from a permutation is that order does not matter. Choosing 2 friends from 4 gives 6 combinations: Ana and Ben is the same as Ben and Ana. To generate combinations without repeats, the function only looks at items after the last one it chose. That is done with a start index, which moves forward.

Press Run. The output is:

[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
count = 6

Here the function uses a loop inside the recursion. The loop tries each item from start onward. Each try is a choose, explore and undo. The argument i + 1 in the explore call means that the next choice must come after this one, so [2, 1] is never built after [1, 2]. The base case fires when the selection has k items, and then the function saves a copy.

Trace the first branch. The loop picks 1, then recurses with start equal to 1. That call picks 2 and reaches length 2, so it saves [1, 2]. It undoes 2, picks 3, and saves [1, 3], then picks 4 and saves [1, 4]. When that loop ends, the call returns, and the first call undoes 1 and picks 2. Each of the six results appears once, in the order the loop finds them.

Python also has this built in. The itertools module, which is part of the standard library, has a function combinations that gives the same groups as tuples:

The output is:

[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
6

In real code, use itertools.combinations. Writing the template yourself is still worth the effort, because a problem often needs a small change that the library cannot make, such as stopping early or pruning a branch. A tuple is a list that cannot be changed, so itertools can return it without a copy step.

The time is O(k * C(n, k)), where C(n, k) is the number of combinations. The stack depth is at most k. You will often need this template when a problem asks for "all groups of size k".

Permutations: try every unused item

A permutation uses every item once, and the order matters. The template is different from subsets. At each position in the answer, the function tries every item that has not been used yet. It needs a used list of True and False flags, one for each item, to know which items are free.

Here is the code that prints every permutation of the letters abc. It builds a list of letters, joins them into a string with "".join when it prints, and prints each arrangement when it is complete:

Press Run. The output is:

abc
acb
bac
bca
cab
cba

Notice the two undo lines at the bottom of the loop. One removes the letter from current, and the other clears the used flag. Both must happen. This is the most common permutation mistake, and the Common mistakes section shows what it costs.

The base case checks whether current has as many letters as the input. When it does, the answer is complete, and the function prints it. The loop tries each letter that has not been used, so each position in the answer has up to n options at the top level, then n - 1, then n - 2, and so on. That gives n! leaves in the tree.

The tree for abc has three branches at the top, one for each first letter. Each of those has two branches for the second letter, and the last level has one branch, which is the whole arrangement. The six leaves are the six lines printed above.

The used list is required. Without it, the function could pick a three times and produce strings like aaa. The continue skips any letter that is already in the answer. A continue in a for loop jumps to the next iteration, so it works as a skip without the nesting of an if block.

The time is O(n! * n), since there are n! arrangements and each takes up to n steps to copy or print. The extra space is O(n) for the used list, the current list and the stack. The output itself takes O(n! * n) space if you save it.

Permutations of a list of numbers

The same template works for a list of numbers. The only change is the type of the items and the way the answer is saved, which needs a copy as before. Here is the version that returns all permutations of [1, 2, 3] as a list of lists:

Press Run. The output is:

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

The standard library has this as well. itertools.permutations returns the same arrangements as tuples, in the same order:

The output is:

[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

This is the template you will reuse most, and you should learn it so well that you can write it without looking. The structure is always the same: a base case that saves a copy, a loop over the choices, a skip for used choices, a choose, an explore, and two undo lines.

What happens when you forget to undo

The most common permutation bug is a missing undo of the used flag. Here is the same code with the line used[i] = False removed. It prints the number of results and the results themselves:

Press Run. The output is:

1 results: [[1, 2, 3]]

Only one result is produced, and six were expected. Trace the first branch. The function chooses 1, then 2, then 3, and saves [1, 2, 3]. Back at the last level, it pops 3 from current, but used[2] stays True. Back at the middle level, it pops 2, but used[1] stays True. Back at the top, it pops 1, but used[0] stays True. Every item is now marked as used, so the loop at every level finds nothing free and does nothing. The function returns having produced one answer.

This failure is quiet. The code runs without any error, and it prints an answer that is short. The lesson to learn is to keep the undo lines paired with the choose lines. Put them next to each other in your head: whatever you add, you must take back.

Duplicates: the rule to remember

What happens if the input has repeated values, such as [1, 1, 2]? The function above produces the same arrangement more than once, because it treats the two 1s as different items. Interviewers often ask about this. The fix is to sort the input first, so that equal values sit next to each other, and then to skip a value when it equals the one before it and that earlier copy is not in use. The rule is one line inside the loop:

if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
    continue

This rule makes sure that equal values are tried in a fixed order, so each distinct arrangement is produced once. Do not memorise it without understanding it. Test it on [1, 1, 2] on paper and count the arrangements. You should get 3: 112, 121 and 211.

The output is:

[[1, 1, 2], [1, 2, 1], [2, 1, 1]]
tuples from itertools: 6
distinct tuples: 3

itertools.permutations treats the two 1s as different items and returns 6 tuples. Putting them in a set removes the repeats and leaves 3. For a small list, a set is a quick fix. The skip rule is better when the arrangements are large, because it never builds the duplicates at all.

Common mistakes

Saving the answer without a copy. The result is a list of references to one changing list, so every entry ends up empty or wrong. The output shows [[], [], [], [], [], [], [], []] for the subsets, as you saw above. The fix is current[:] or list(current). If you only need text, "".join(current) makes a new string, and strings never change.

Forgetting to undo a choice. A missing pop or missing used[i] = False leaves stale state for later branches. The output for permutations was 1 results: [[1, 2, 3]] instead of six results. Check each choose against its undo.

Undoing only one of two changes. In permutations you change two things, the list and the flag. Undoing one but not the other is still a bug, as the last section showed.

Using the wrong start index. In combinations, starting the loop at 0 instead of start produces repeated groups in a different order, such as both [1, 2] and [2, 1]. Check the start index on each call.

Building a list of lists with *. This is a Python trap that is not a recursion bug, but it breaks the used lists and the answers in the same way. The expression [[]] * 3 makes three references to one inner list, so an append to one shows up in all three:

The output is:

[[1, 2], [1, 2], [1, 2]]
[[1, 2], [1], [1]]

Use [False] * 3 for a flat list of flags, because a flag is a value that cannot change in place. Use a list comprehension, as in the second line, when each element must be its own list.

Forgetting the base case for a subset. If the base case stops early, you save partial subsets. If it never stops, Python raises RecursionError. Trace the smallest list, which is empty, and check the answer for that case: one subset, the empty one.

Ignoring duplicates. If the problem says the input may contain repeats, the plain template gives duplicate answers. Read the statement carefully, and ask the interviewer whether repeats should be removed.

Debugging walkthrough

Suppose a permutation counter has no undo for the used flags, so it returns 1 for [1, 2, 3] instead of 6. Use the method from the first lesson: name the expected answer first, which is 6, and then find the input where the function goes wrong. Start with the smallest input that can show the problem, which is a list of two items. For [1, 2] the answer should be 2.

Write the code on paper with a used flag, and trace it. Choose 1, mark used[0], recurse. The next level picks 2, reaches the base case, and returns. Back at the top, the code now looks at i = 1. But used[1] is still True because the code has no undo line, so the loop skips item 2 and never starts an arrangement with it. Only one arrangement is found, [1, 2], and the answer is 1, not 2.

Add a print line on entry to watch the calls, the way the first lesson did. The trace shows that the top level's second iteration finds nothing to do, and the cause is the flag left behind. The fix is the missing used[i] = False. Check the fix on [1, 2] first, then on [1, 2, 3]. Only after the small case works should you trust the big one.

Cost in plain numbers

Subsets: 2^n answers, O(2^n * n) time if you copy each one, O(n) stack space. Counting subsets that hit a target: O(2^n) time and O(n) space, with no list of answers stored. Combinations of size k: O(k * C(n, k)) time, and O(k) stack space. Permutations: n! answers, O(n! * n) time, and O(n) extra space for the flags and the stack, not counting the answers you save.

These numbers tell you what is possible. A list of 20 items has about a million subsets, which is fine, and about 2.4 quintillion permutations, which is not. When a problem gives you 20 items and asks for every permutation, the answer is that no method can list them all in time, so the question is probably about counting or about a rule that cuts the tree down. That leads to the pruning idea of the next lesson.

Interview and real-world uses

In interviews, the standard follow-up questions are these: "What is the time complexity?", "How do you handle duplicates?", "Can you count instead of list?" and "Can you stop early when you find one answer?" For each, you should be able to point to the template and say which line changes. The count version drops the save. The duplicate version adds the skip rule after sorting. The one-answer version returns True as soon as an answer is found, and the parent call stops its loop.

In real software, subsets and permutations appear in planning tools that look for every combination of parts, in test generators that try every ordering of steps, in scheduling problems, and in puzzle solvers. Production code for large inputs uses smarter methods, such as dynamic programming or heuristics, but the first correct version is almost always a backtracking search. In Python, itertools covers the plain cases, and the template covers the rest.

Following every save in order

The subset template is easier to trust once you have watched the order of its saves. Take the list [1, 2, 3], and read the decisions as a path from the top of the tree. Each decision is either s (skip) or t (take), made for 1, then 2, then 3. The path s s s reaches the base case with nothing chosen, so the function saves []. The path s s t saves [3]. The path s t s saves [2], and s t t saves [2, 3]. The paths that start with t come next, so t s s saves [1], t s t saves [1, 3], t t s saves [1, 2], and t t t saves [1, 2, 3].

That is exactly the order the program prints, [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]. The reason is that the function always explores the skip branch of a decision before the take branch. Every leaf in the skip half of the tree is saved before any leaf in the take half. This kind of order, where a whole branch finishes before the next one starts, is called depth-first. You will meet it again in the graph and tree modules, where the same rule decides the order in which nodes are visited.

Knowing the order also lets you check a result without the full list. If you know the first result must be the empty subset, and the last must be the full list, you can test those two lines first. A wrong order often means that a skip and a take were swapped, or that the undo ran in the wrong place.

Walking through an interview question about subsets

Suppose an interviewer asks: "Given a list of numbers, find how many groups of them add up to a target." The word "groups" is a hint that subsets are the right tool, and the words "how many" are a hint that you may not need to list them.

Start by asking one question back: does the list need to be printed, or only counted? Assume counting, and say so out loud. Then describe the decision: each number is either in the group or out of it. Name the base case: the end of the list, where the group is complete and you check its sum. State the running total as a parameter, so that no undo is needed. Write the function, trace it on a small list such as [2, 2] with target 2, which has two groups, and state the cost: O(2^n) time, because every group is visited once, and O(n) stack space.

The interviewer may then ask for a faster method. A strong answer explains that a counting table indexed by the running sum can do the job in time that depends on the target rather than on 2^n, when the numbers are small non-negative whole numbers. You do not need to write that table in the interview unless asked. Naming it, and explaining when it works, is enough to show that you know the limit of the method you wrote.

A checklist for backtracking templates

Before you trust a backtracking function, check each of these points. Each point has caught real bugs in the examples above.

• Does the base case save or count exactly one complete answer?
• Is each saved answer a copy, or a value that cannot change later?
• Is every choice undone right after its explore call, in the reverse order it was made?
• Does every flag or counter that the choose step changes get restored in the undo step?
• Does the loop start at the right index, 0 for permutations and start for combinations?
• Does the function handle the empty list, where the only answer is the empty subset?
• Do you know the cost in terms of the number of answers?

Run through this list before you run the code. A minute spent on it is cheaper than an hour spent on a result that looks plausible and is wrong.

Questions learners ask about backtracking

Why does the subset function need a copy, but the sum counter does not? The subset function keeps its answer in one shared list, so every saved result must be a copy. The sum counter keeps its state in a parameter, one value per call, and returns a number instead of saving a list. A number cannot change after it is returned, so no copy is needed. Ask what the saved thing is, and whether it can change later.

How do I know my undo is complete? After the top-level call returns, the shared state should look as it did before the call. For the permutation function, every entry of used should be False again, and the list current should be empty. Add that check to a test, and it will catch a missing undo the first time. The buggy version in this lesson leaves used full of True values, which is the sign of a missing used[i] = False.

Is backtracking just brute force? It is a careful form of brute force. Brute force tries every possibility from start to finish. Backtracking tries the possibilities in a tree, and it can skip a whole branch when a rule shows that it cannot help. Without a check, backtracking is the same as brute force, and the check is what makes the search practical. That is why the next lesson focuses on pruning.

Practice

Exercise 1 (easy). Trace the subsets code by hand for [1, 2]. Write down the four results and the order in which they are saved. Hint: the first saved result is the empty list.

Show the answer

The results are [], [2], [1] and [1, 2], in that order. The first call skips 1 and 2 and saves []. Back at index 1, it takes 2 and saves [2]. Back at the top, it takes 1 and then skips 2, saving [1], and then takes 2, saving [1, 2].

Exercise 2 (easy). Predict the number of permutations of four distinct letters, then count them by writing the formula. Hint: 4 choices, then 3, then 2, then 1.

Show the answer

4 * 3 * 2 * 1 = 24. The first position has 4 options, the second has 3 left, and so on. The backtracking tree has 24 leaves. Check it with len(list(itertools.permutations("abcd"))).

Exercise 3 (easy). Remove the append and pop lines from the subsets code, and predict what the program prints. Then run it. Explain the result in one sentence.

Show the answer

Without the appends, current never changes, so every saved result is the empty list. The program prints eight empty lists, [[], [], [], [], [], [], [], []]. The reason is that the function never chooses anything, so every leaf saves the same empty selection.

Exercise 4 (medium). Write a function that prints every subset of [1, 2, 3] whose sum equals a target. Print each matching subset. Test it with a target of 3.

Show the answer

def print_matching(nums: list[int], i: int, total: int, target: int, current: list[int]) -> None:
    if i == len(nums):
        if total == target:
            print(current)
        return
    print_matching(nums, i + 1, total, target, current)
    current.append(nums[i])
    print_matching(nums, i + 1, total + nums[i], target, current)
    current.pop()
 
 
print_matching([1, 2, 3], 0, 0, 3, [])  # prints [3] then [1, 2]

The base case checks the sum and prints only the matching subsets. The pop line keeps current right for the next branch. The output is [3] and then [1, 2].

Exercise 5 (medium). Count the permutations of [1, 2, 3, 4] without listing them, using a counter instead of a list. Hint: return 1 at the base case and add up the counts from the children. Check that the answer is 24.

Show the answer

def count_perms(nums: list[int], used: list[bool], depth: int) -> int:
    if depth == len(nums):
        return 1
    total = 0
    for i in range(len(nums)):
        if used[i]:
            continue
        used[i] = True
        total += count_perms(nums, used, depth + 1)
        used[i] = False
    return total
 
 
print(count_perms([1, 2, 3, 4], [False] * 4, 0))  # 24

Each leaf returns 1, and each level adds up its children. The total is 24.

Exercise 6 (medium). Write a function that prints all combinations of 3 letters from abcde, one per line. Predict how many lines you will see before you run it. Hint: use the start index template from this lesson.

Show the answer

def combos(letters: str, start: int, k: int, current: list[str]) -> None:
    if len(current) == k:
        print("".join(current))
        return
    for i in range(start, len(letters)):
        current.append(letters[i])
        combos(letters, i + 1, k, current)
        current.pop()
 
 
combos("abcde", 0, 3, [])

There are 10 lines, which is C(5, 3). The first is abc and the last is cde.

Exercise 7 (medium). Explain why the explore call in the combination template uses i + 1 and not start + 1. Give the output you would get with start + 1, for [1, 2, 3] and k equal to 2.

Show the answer

i + 1 means the next choice must come after the one just made, so each group appears once in increasing order. With start + 1 the next call begins its loop one place after the parent's start, not after the item just chosen, so it can pick the same item again and can go back to an earlier one. Running that version prints [[1, 2], [1, 3], [2, 2], [2, 3], [3, 2], [3, 3]]. The pairs [2, 2] and [3, 3] reuse an item, and [3, 2] repeats the pair [2, 3] in a different order. The i + 1 form gives only [1, 2], [1, 3] and [2, 3].

Exercise 8 (hard). Write a function that returns True as soon as it finds one permutation of [1, 2, 3] whose first element is 2. Hint: return True from the recursion and stop the loop. A return inside a loop stops the loop too.

Show the answer

def find_with_first_two(nums: list[int], used: list[bool], current: list[int]) -> bool:
    if len(current) == len(nums):
        return current[0] == 2
    for i in range(len(nums)):
        if used[i]:
            continue
        used[i] = True
        current.append(nums[i])
        if find_with_first_two(nums, used, current):
            return True
        current.pop()
        used[i] = False
    return False
 
 
cur: list[int] = []
print(find_with_first_two([1, 2, 3], [False] * 3, cur), cur)  # True [2, 1, 3]

The return True leaves the loop and every parent call at once, so the search stops at the first match. The undo lines run only when a branch fails, so a True answer keeps its state. The first complete arrangement that starts with 2 is [2, 1, 3].

Exercise 9 (hard). Explain how to adapt the permutation template so that it skips duplicate arrangements for [1, 1, 2]. Write the sorted version of the code, add the skip rule, and predict the three results before running it.

Show the answer

Sort the input first: sorted([1, 1, 2]) gives [1, 1, 2]. Add the rule if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]: continue at the top of the loop. The three results are [1, 1, 2], [1, 2, 1] and [2, 1, 1]. The rule makes the second 1 wait until the first 1 is in use, so the same arrangement is never built twice.

Exercise 10 (hard). Explain in a paragraph why the number of subsets of a 20-item list is about a million, but the number of permutations is far too large to list. Use the numbers 2^20 and 20!, and say what a backtracking function could do instead for a question that only asks for a count.

Show the answer

2^20 is 1,048,576, about a million, so listing every subset takes a second or so. 20! is about 2.4 times 10^18, which is far too many to list or even count one by one in a normal lifetime. A function that only needs a count can avoid listing by returning numbers up the recursion, as the target-sum counter does. For permutations, a count of all arrangements is simply n!, and a count with a rule usually needs pruning or a smarter table, which the next lesson introduces.

What you now know

• Backtracking builds an answer one choice at a time. The pattern is choose, explore, undo, and the undo step restores the state for the next branch.
• Subsets are built by skipping or taking each item, so a list of n items has 2^n subsets.
• Save a copy of a finished answer with current[:], or it will change under you.
• Count instead of listing when the question asks how many. Pass a running total down the recursion and return a count.
• Combinations use a start index and explore with i + 1, which gives each group once. itertools.combinations gives the same groups.
• Permutations use a used list. Undo both the list and the flag every time. itertools.permutations gives the same arrangements.
• Duplicates in the input need a sorted list and a skip rule inside the loop.
• Subsets cost O(2^n * n) to list and permutations cost O(n! * n), so these functions work only for small inputs unless you prune or count.