Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Backtracking: Permutations and Partitions

Editorial

Order matters now

Subsets asked which values to take. Permutations ask in what order: [1, 2, 3] and [3, 2, 1] are different answers. So the decision changes. Instead of take or skip, each position picks one of the values not used yet: three choices for the first position, two for the second, one for the last. That's 3 × 2 × 1 = 6 orders, n! in general, and n! grows much faster than 2ⁿ: 10 values have 3,628,800 orders against 1,024 subsets.

A tree of shaded discs for the permutations of [1, 2, 3]. At the top a slate tile reads empty. Its three children are discs 1, 2 and 3; under each, two discs hold the values still unused, and under each of those one disc holds the last value, every value keeping its own colour. Down the left, the levels are labelled position 0 with 3 free, position 1 with 2 free and position 2 with 1 free. Under the bottom discs, six tiles hold the orders 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2 and 3 2 1, with 3 × 2 × 1 = 6 orders written at their left. One path is drawn thick in purple, 2, then 3, then 1, its discs ringed, ending at the ringed tile 2 3 1, with a pill under it reading 2, then 3, then 1. Focal line: each position takes an unused value: n values, n! orders. Title: each position takes an unused value.

Mark it used, unmark it on the way back

A used array says which values are already placed. Each call loops over every value, skips the used ones, and for each free one: marks it, appends it, explores the next position, then undoes both. When the path holds every value, it's one permutation:

void place(const vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& out) {
    if (path.size() == nums.size()) {                 // every position filled
        out.push_back(path);
        return;
    }
    for (int i = 0; i < (int)nums.size(); i++) {
        if (used[i]) continue;                        // already placed earlier in this order
        used[i] = true;                               // choose
        path.push_back(nums[i]);
        place(nums, used, path, out);                 // explore
        path.pop_back();                              // unchoose, both marks
        used[i] = false;
    }
}

vector<vector<int>> permute(const vector<int>& nums) {
    vector<vector<int>> out;
    vector<bool> used(nums.size(), false);
    vector<int> path;
    place(nums, used, path, out);
    return out;
}

def permute(nums):
    out, path, used = [], [], [False] * len(nums)

    def place():
        if len(path) == len(nums):              # every position filled
            out.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue                        # already placed earlier in this order
            used[i] = True                      # choose
            path.append(nums[i])
            place()                             # explore
            path.pop()                          # unchoose, both marks
            used[i] = False

    place()
    return out

static void place(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> out) {
    if (path.size() == nums.length) {                 // every position filled
        out.add(new ArrayList<>(path));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;                        // already placed earlier in this order
        used[i] = true;                               // choose
        path.add(nums[i]);
        place(nums, used, path, out);                 // explore
        path.remove(path.size() - 1);                 // unchoose, both marks
        used[i] = false;
    }
}

static List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> out = new ArrayList<>();
    place(nums, new boolean[nums.length], new ArrayList<>(), out);
    return out;
}

function permute(nums) {
    const out = [], path = [], used = new Array(nums.length).fill(false);
    function place() {
        if (path.length === nums.length) {            // every position filled
            out.push([...path]);
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue;                    // already placed earlier in this order
            used[i] = true;                           // choose
            path.push(nums[i]);
            place();                                  // explore
            path.pop();                               // unchoose, both marks
            used[i] = false;
        }
    }
    place();
    return out;
}

Each printed [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]. Unlike subsets, there's no start index: a later position may take an earlier value, as long as it's free. The calls add up quickly:

ValuesPermutations, n!Calls
42465
5120326
67201,957
75,04013,700
840,320109,601

That's 2.72 calls per permutation at 8 values, the number e (2.718…), so the work is about e × n! calls plus copying each permutation out. Another way to build them swaps values into place instead of marking them:

def permute_in_place(nums):
    out = []

    def fill(i):
        if i == len(nums):
            out.append(nums[:])
            return
        for j in range(i, len(nums)):
            nums[i], nums[j] = nums[j], nums[i]   # bring nums[j] to position i
            fill(i + 1)
            nums[i], nums[j] = nums[j], nums[i]   # and put it back

    fill(0)
    return out

Position i takes each value from i onward by swapping it in, and swaps it back after. No used array, and it returned the same 6 permutations, listed in a slightly different sequence. The used version is easier to adapt, because the values stay where they are: the next section relies on that.

Twins go in order

Permutations II allows repeated values. The code above, run on [1, 1, 2], returned [[1, 1, 2], [1, 2, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 1, 1]]: each of the 3 real orders twice, once with the first 1 placed first and once with the second. Sort the values so twins sit side by side, and let them into the path only in their left-to-right order: skip a value whose twin to the left isn't placed yet.

The tree Permutations II builds for the sorted [1, 1, 2], each disc the index a position took: #0 and #1 are 1s, drawn blue, and #2 is the 2, drawn orange. From a slate tile reading empty, edges lead to #0 and #2, and a dashed red edge leads to a pale #1 tagged waits for #0. Under #0, the path goes on to #1 then #2, and to #2 then #1; under #2 it goes on to #0 then #1, while #1 is refused again, tagged waits for #0. Green tiles under the three full paths read 1 1 2, 1 2 1 and 2 1 1. At the right, the sorted values 1, 1, 2 sit over their indexes #0, #1, #2; a ticked card reads 3 orders, each once: [1, 1, 2], [1, 2, 1], [2, 1, 1]; a crossed card reads no rule: 6, each order twice, once with #0 first, once with #1 first. Focal line: a twin waits until the one to its left is placed. Title: twins go in order.
void place(const vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& out) {
    if (path.size() == nums.size()) {
        out.push_back(path);
        return;
    }
    for (int i = 0; i < (int)nums.size(); i++) {
        if (used[i]) continue;
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;   // its twin to the left goes first
        used[i] = true;
        path.push_back(nums[i]);
        place(nums, used, path, out);
        path.pop_back();
        used[i] = false;
    }
}

vector<vector<int>> permuteUnique(vector<int> nums) {
    sort(nums.begin(), nums.end());                   // twins side by side
    vector<vector<int>> out;
    vector<bool> used(nums.size(), false);
    vector<int> path;
    place(nums, used, path, out);
    return out;
}

def permute_unique(nums):
    nums = sorted(nums)                          # twins side by side
    out, path, used = [], [], [False] * len(nums)

    def place():
        if len(path) == len(nums):
            out.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue                         # its twin to the left goes first
            used[i] = True
            path.append(nums[i])
            place()
            path.pop()
            used[i] = False

    place()
    return out

static void place(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> out) {
    if (path.size() == nums.length) {
        out.add(new ArrayList<>(path));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;   // its twin to the left goes first
        used[i] = true;
        path.add(nums[i]);
        place(nums, used, path, out);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

static List<List<Integer>> permuteUnique(int[] nums) {
    int[] sorted = nums.clone();
    Arrays.sort(sorted);                              // twins side by side
    List<List<Integer>> out = new ArrayList<>();
    place(sorted, new boolean[sorted.length], new ArrayList<>(), out);
    return out;
}

function permuteUnique(nums) {
    const sorted = [...nums].sort((a, b) => a - b);   // twins side by side
    const out = [], path = [], used = new Array(sorted.length).fill(false);
    function place() {
        if (path.length === sorted.length) {
            out.push([...path]);
            return;
        }
        for (let i = 0; i < sorted.length; i++) {
            if (used[i]) continue;
            if (i > 0 && sorted[i] === sorted[i - 1] && !used[i - 1]) continue;   // its twin to the left goes first
            used[i] = true;
            path.push(sorted[i]);
            place();
            path.pop();
            used[i] = false;
        }
    }
    place();
    return out;
}

Each took [1, 2, 1], sorted it, and printed [[1, 1, 2], [1, 2, 1], [2, 1, 1]]. Step through it:

Twins in order, on [1, 1, 2] — Green values are in the path; indigo is the one being placed; grey is a twin skipped because the one to its left is still free. The row below is the path.

Why it's correct: two arrangements that differ only in which 1 went where are the same permutation, and the rule keeps exactly one of them, the one where the 1s were placed left to right. The opposite rule, skip when the twin to the left is placed, keeps the right-to-left one, and is also correct. But it refuses late: a path that places the left twin first isn't cut on the spot; it dies further down, once the right twin can never be placed. On [1, 1, 1, 2, 2, 2, 3, 3] both built the 560 distinct orders, the left-to-right rule in 1,749 calls and the right-to-left one in 8,496, 4.9 times as many.

Below, you run it yourself. At each position, place the next index the loop allows, record a full path, or back up. A twin placed before the one to its left is refused, with the reason, and the outline grows the tree as you go.

Place the Twins: you run Permutations II

Where does the next piece end

Palindrome Partitioning cuts a string into pieces that are all palindromes. The choice changes again: the next piece starts where the last one ended, and the call decides where it ends. Every end that makes the piece a palindrome is a branch; when the pieces reach the end of the string, they're one answer:

The tree Palindrome Partitioning searches for the string aab, shown in a slate tile at the top. From it, edges lead to the pieces a and aa in blue tiles and to aab, pale and dashed red, tagged baa backwards. Beside a, a label reads rest "ab"; under it the pieces a, with rest "b" beside it, and ab, pale and dashed red, tagged ba backwards. Under the second a the piece b leads to a green tile reading a | a | b; beside aa a label reads rest "b", and under it the piece b leads to a green tile reading aa | b. At the right, a ticked card reads 2 partitions, a | a | b and aa | b, the pieces cover the whole string; a crossed card reads 2 pieces refused, aab and ab change when read backwards, so nothing grows under them. Focal line: the next piece starts where the last one ended. Title: each piece must be a palindrome.
void cut(const string& s, int start, const vector<vector<bool>>& pal, vector<string>& path,
         vector<vector<string>>& out) {
    if (start == (int)s.size()) {                     // the pieces cover the whole string
        out.push_back(path);
        return;
    }
    for (int end = start; end < (int)s.size(); end++) {
        if (!pal[start][end]) continue;               // this piece isn't a palindrome
        path.push_back(s.substr(start, end - start + 1));
        cut(s, end + 1, pal, path, out);              // the rest starts right after it
        path.pop_back();
    }
}

vector<vector<string>> partition(const string& s) {
    int n = s.size();
    vector<vector<bool>> pal(n, vector<bool>(n, false));   // pal[i][j]: is s[i..j] a palindrome
    for (int i = n - 1; i >= 0; i--)
        for (int j = i; j < n; j++)
            pal[i][j] = s[i] == s[j] && (j - i < 2 || pal[i + 1][j - 1]);
    vector<vector<string>> out;
    vector<string> path;
    cut(s, 0, pal, path, out);
    return out;
}

def partition(s):
    n = len(s)
    pal = [[False] * n for _ in range(n)]       # pal[i][j]: is s[i..j] a palindrome
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1])
    out, path = [], []

    def cut(start):
        if start == n:                          # the pieces cover the whole string
            out.append(path[:])
            return
        for end in range(start, n):
            if not pal[start][end]:
                continue                        # this piece isn't a palindrome
            path.append(s[start:end + 1])
            cut(end + 1)                        # the rest starts right after it
            path.pop()

    cut(0)
    return out

static void cut(String s, int start, boolean[][] pal, List<String> path, List<List<String>> out) {
    if (start == s.length()) {                        // the pieces cover the whole string
        out.add(new ArrayList<>(path));
        return;
    }
    for (int end = start; end < s.length(); end++) {
        if (!pal[start][end]) continue;               // this piece isn't a palindrome
        path.add(s.substring(start, end + 1));
        cut(s, end + 1, pal, path, out);              // the rest starts right after it
        path.remove(path.size() - 1);
    }
}

static List<List<String>> partition(String s) {
    int n = s.length();
    boolean[][] pal = new boolean[n][n];              // pal[i][j]: is s[i..j] a palindrome
    for (int i = n - 1; i >= 0; i--)
        for (int j = i; j < n; j++)
            pal[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i + 1][j - 1]);
    List<List<String>> out = new ArrayList<>();
    cut(s, 0, pal, new ArrayList<>(), out);
    return out;
}

function partition(s) {
    const n = s.length;
    const pal = Array.from({length: n}, () => new Array(n).fill(false));   // pal[i][j]: is s[i..j] a palindrome
    for (let i = n - 1; i >= 0; i--)
        for (let j = i; j < n; j++)
            pal[i][j] = s[i] === s[j] && (j - i < 2 || pal[i + 1][j - 1]);
    const out = [], path = [];
    function cut(start) {
        if (start === n) {                            // the pieces cover the whole string
            out.push([...path]);
            return;
        }
        for (let end = start; end < n; end++) {
            if (!pal[start][end]) continue;           // this piece isn't a palindrome
            path.push(s.slice(start, end + 1));
            cut(end + 1);                             // the rest starts right after it
            path.pop();
        }
    }
    cut(0);
    return out;
}

Each printed [["a", "a", "b"], ["aa", "b"]] for "aab" and [["a", "b", "b", "a"], ["a", "bb", "a"], ["abba"]] for "abba". The table pal is filled once before the search: s[i..j] is a palindrome when its two end letters match and the part between them is one, and a piece of one or two letters only needs the ends to match. Filling it from the last start back to the first means the part between is always known already. Then every check is a lookup instead of a reversal.

A string of one repeated letter is the worst case: every piece is a palindrome, so each of the 15 gaps is cut or not, 32,768 partitions for 16 letters, the problem's limit. Checking each piece by reversing it took 42 ms in Python; with the table, 21 ms.

Carrying state from piece to piece

Expression Add Operators puts +, - or * between the digits of a string so the expression hits a target, and a number can span several digits. The pieces are chosen the same way, where each number ends, but now each call also carries the value so far and the last operand. Plus and minus are simple, and after a minus the last operand is negative. Times has to bind tighter: undo the last operand and multiply it in, value - last + last * cur. After 1+2 the value is 3 and the last operand 2, so *3 makes it 3 − 2 + 2 × 3 = 7, which is what 1+2*3 is:

def add_operators(num, target):
    out = []

    def build(start, expr, value, last):
        if start == len(num):
            if value == target:
                out.append(expr)
            return
        for end in range(start, len(num)):
            if end > start and num[start] == "0":
                break                           # a number can't start with 0, unless it is 0
            piece = num[start:end + 1]
            cur = int(piece)
            if start == 0:
                build(end + 1, piece, cur, cur)
            else:
                build(end + 1, expr + "+" + piece, value + cur, cur)
                build(end + 1, expr + "-" + piece, value - cur, -cur)
                # undo the last operand, then multiply it in: * binds tighter than + and -
                build(end + 1, expr + "*" + piece, value - last + last * cur, last * cur)

    build(0, "", 0, 0)
    return out

For "123" and 6 it returned ['1*2*3', '1+2+3']; for "232" and 8, ['2*3+2', '2+3*2']; for "105" and 5, ['1*0+5', '10-5']; and for "3456237490" and 9191, nothing. Ten digits can make 9,999,999,999, past a 32-bit int, so Java and C++ need long for the value, the last operand and each number.

Spotting it, and when it breaks

The clues. "All orderings", "all arrangements", "every way to split", "insert operators": the order matters, or the input is cut into pieces whose boundaries you choose. Inputs are tiny, 6 to 10 values or digits, or up to 16 letters, because the number of answers explodes with each extra one.

The near-misses. Order doesn't matter: subsets and combinations (Backtracking: Subsets and Combinations). Only the number of partitions, or the fewest pieces: a table over positions, not a search (Interval and Partition DP).

When it breaks. n! runs out of road fast: 12 values have 479,001,600 orders, and listing them is already the cost. If the question is only how many, count them with a formula instead of building them: n! divided by the factorial of each repeat count, so [1, 1, 1, 2, 2, 2, 3, 3] has 8! / (3! × 3! × 2!) = 560.

Bugs that cost a submission

Forgetting to unmark.

used[i] = True
path.append(nums[i])
place()
path.pop()                          # but used[i] stays True

permute([1, 2, 3]) returned [[1, 2, 3]]: after the first permutation every value stays used, so no other branch can place anything.

The twin test without not used[i - 1].

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

permute_unique([1, 1, 2]) returned []. It skips the second 1 even when the first is already placed, the one case where it has to be allowed, so no path can ever hold both 1s.

A number with a leading zero.

for end in range(start, len(num)):
    piece = num[start:end + 1]     # no check for "05"

For "105" and 5 it returned ['1*0+5', '1*05', '10-5'], with 1*05 among them: 05 isn't a number in an expression. Stop at a leading 0 unless the piece is the 0 itself.

int for the running value (Java).

static void build(String num, long target, int start, String expr, int value, int last, List<String> out)

addOperators("2147483648", -2147483648) returned [2147483648] with int: 2,147,483,648 wrapped around to −2,147,483,648 and matched. With long it returned [].

Check yourself

Quiz

1 / 6

Multiple choice

How many permutations does [1, 2, 3, 4] have?

Practice problems

In this order:

  1. Permutations: mark, explore, unmark.
  2. Permutations II: sort, and place twins in order.
  3. Palindrome Partitioning: choose where each piece ends, with the palindrome table.
  4. Expression Add Operators: choose where each number ends, and carry the last operand for *.

Next, Backtracking on Grids and Constraints: placing under rules, and cutting as early as you can.