These are the notes for DSA episode 31, the first backtracking episode. Until now every problem asked for one best answer. Here the problem asks for every answer: every subset of a set of items, and every permutation (ordering) of them. Nested loops can't do it, because the number of loops is fixed when you write the code. Counting through every sequence works for any n, but builds nⁿ sequences to keep n! and times out at n = 10. The fix is recursion over a decision tree, with the three-step pattern choose → explore → un-choose. Subsets cost O(n·2ⁿ) and permutations O(n·n!): exactly the size of the answer. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.
The problem, in real life
A thali counter offers three extras on top of the meal: papad, raita and a sweet. You may take any mix of them, from none to all three. Each extra is a yes or a no: 2 × 2 × 2 = 8 different thalis. The owner wants a menu card listing all eight.
Three friends, Asha, Ravi and Neha, get three movie seats in a row. The first seat can take any of the 3, the second any of the 2 left, the last gets whoever remains: 3 × 2 × 1 = 6 seating orders.
| In real life | In the code |
|---|---|
| The extras (papad, raita, sweet) | The input array a = [1, 2, 3] |
| One thali (a mix of extras) | One subset |
| The menu card of every thali | The list of all subsets (the power set) |
| One seating of the friends | One permutation |
| "Is this friend already seated?" | The used[] array |
| Deciding extra by extra, seat by seat | One level of the decision tree per item |
Problem statement
Subsets (LeetCode 78). Given an array of distinct integers, return all possible subsets. Order doesn't matter inside a subset, and the answer must not contain duplicate subsets.
subsets([1, 2, 3]) → [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []] (8 = 2³ subsets)
subsets([]) → [[]]
subsets([5]) → [[5], []]
Permutations (LeetCode 46). Given an array of distinct integers, return all possible orderings.
perms([1, 2, 3]) → [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] (6 = 3!)
perms([7]) → [[7]]
perms([]) → [[]]
Edge cases: the empty array (one subset and one permutation: the empty list), a single element. Constraints: n is small (up to about 10 for permutations, about 20 for subsets), because the answer itself grows exponentially. But n is not fixed: the code must work for any n.
The obvious way 1: one nested loop per item
Each extra is a yes (1) or no (0), so give each extra a loop that runs twice.
public class Main {
public static void main(String[] args) {
String[] e = {"papad", "raita", "sweet"};
int count = 0;
for (int a = 0; a < 2; a++)
for (int b = 0; b < 2; b++)
for (int c = 0; c < 2; c++) {
String t = "";
if (a == 1) t += e[0] + " ";
if (b == 1) t += e[1] + " ";
if (c == 1) t += e[2] + " ";
System.out.println("[" + t.trim() + "]");
count++;
}
System.out.println(count + " thalis");
}
}
Output:
[]
[sweet]
[raita]
[raita sweet]
[papad]
[papad sweet]
[papad raita]
[papad raita sweet]
8 thalis
Correct for three extras. Now add a fourth one, "salad", to the array and run it again: it still prints the same 8 thalis, and salad never appears. Four extras need 16 thalis and a fourth loop typed by hand. The number of loops is fixed when you write the code, but n is only known when the program runs.
The obvious way 2: count through every sequence (the odometer)
For orders, number the friends 0 … n-1, count through every sequence of n digits like an odometer (000, 001, …, 222), and keep only sequences where no digit repeats.
static long brute(int n) {
int[] d = new int[n];
long count = 0;
while (true) {
boolean[] seen = new boolean[n];
boolean ok = true;
for (int x : d) {
if (seen[x]) { ok = false; break; }
seen[x] = true;
}
if (ok) count++;
int k = n - 1;
while (k >= 0 && d[k] == n - 1) d[k--] = 0;
if (k < 0) return count;
d[k]++;
}
}
brute(3) prints 6. Correct.
The big input: 10 friends
long t0 = System.nanoTime();
long ans = brute(10);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println(ans + " orders, " + ms + " ms");
Result: Time Limit Exceeded (more than 8 seconds).
Why the brute force fails
| n | n! (real orders) | nⁿ (sequences checked) |
|---|---|---|
| 3 | 6 | 27 |
| 8 | 40,320 | 1,67,77,216 |
| 10 | 36,28,800 (36 lakh) | 10,00,00,00,000 (1000 crore) |
More than 99.9% of the sequences repeat a friend and are thrown away. The odometer builds a whole sequence before checking it. We want code that:
- goes exactly n levels deep, where n is decided at run time, and
- stops building an order the moment it becomes invalid.
The key insight: recursion over a decision tree
Recursion is a function that calls itself on a smaller version of the same problem. Write one function that decides one item, then calls itself to decide the rest. With 10 items it goes 10 calls deep by itself: the depth comes from the data, not from how many loops you typed. Every recursion needs a base case, the point where it stops: here, "no items left to decide", and the choices so far are one complete answer.
Draw the calls as a tree, the decision tree (also called the recursion tree):
[]
+1 / \ skip 1
[1] []
+2 / \ skip 2 +2 / \ skip 2
[1,2] [1] [2] []
/ \ / \ / \ / \
[1,2,3] [1,2] [1,3] [1] [2,3] [2] [3] [] ← 8 leaves = 8 subsets
Each level decides one item. Every leaf is one complete answer. To move from the leaf [1, 2, 3] to the next leaf [1, 2], you don't start again from the top: you step back up one level, undo the choice of 3, and take the other branch. Stepping back and undoing your last choice is backtracking.
Backtracking in three steps
- Choose: add the item to the current list
cur. - Explore: recurse to decide everything after it.
- Un-choose: remove the item again, so
curis exactly as before; then try the other branch.
At a leaf, save a copy of cur, because cur keeps changing after you leave the leaf.
For permutations, each level asks a different question: which unused number goes in the next seat? A boolean[] used remembers who is already seated, so a branch that repeats a number is never started:
[]
/ | \
[1] [2] [3]
/ \ / \ / \
[1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
| | | | | |
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1] ← 6 leaves = 6 orders
The optimal solution in Java
Subsets
import java.util.*;
public class Main {
static void pick(int[] a, int i, List<Integer> cur,
List<List<Integer>> out) {
if (i == a.length) {
out.add(new ArrayList<>(cur));
return;
}
cur.add(a[i]);
pick(a, i + 1, cur, out);
cur.remove(cur.size() - 1);
pick(a, i + 1, cur, out);
}
static List<List<Integer>> subsets(int[] a) {
List<List<Integer>> out = new ArrayList<>();
pick(a, 0, new ArrayList<>(), out);
return out;
}
public static void main(String[] args) {
System.out.println(subsets(new int[]{1, 2, 3}));
System.out.println(subsets(new int[]{}));
System.out.println(subsets(new int[]{5}));
System.out.println(subsets(new int[]{1, 2, 3, 4}).size());
}
}
Output:
[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
[[]]
[[5], []]
16
The 8 subsets come out in the same order as the leaves of the tree (take before skip). Four items give 16 with no new loop.
Permutations
import java.util.*;
public class Main {
static void build(int[] a, boolean[] used, List<Integer> cur,
List<List<Integer>> out) {
if (cur.size() == a.length) {
out.add(new ArrayList<>(cur));
return;
}
for (int i = 0; i < a.length; i++) {
if (used[i]) continue;
used[i] = true;
cur.add(a[i]);
build(a, used, cur, out);
cur.remove(cur.size() - 1);
used[i] = false;
}
}
static List<List<Integer>> perms(int[] a) {
List<List<Integer>> out = new ArrayList<>();
build(a, new boolean[a.length], new ArrayList<>(), out);
return out;
}
public static void main(String[] args) {
System.out.println(perms(new int[]{1, 2, 3}));
System.out.println(perms(new int[]{7}));
System.out.println(perms(new int[]{}));
System.out.println(perms(new int[]{1, 2, 3, 4}).size());
}
}
Output:
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
[[7]]
[[]]
24
The big input again: 10 friends
The same backtracking, counting the orders instead of storing 36 lakh lists:
static long count(int n, boolean[] used, int placed) {
if (placed == n) return 1;
long c = 0;
for (int i = 0; i < n; i++) {
if (used[i]) continue;
used[i] = true;
c += count(n, used, placed + 1);
used[i] = false;
}
return c;
}
count(10, new boolean[10], 0) prints 3628800 orders, 57 ms (the time varies a little run to run). The odometer didn't finish in 8 seconds.
The same solution in C++
#include <bits/stdc++.h>
using namespace std;
void pick(const vector<int>& a, int i, vector<int>& cur, vector<vector<int>>& out) {
if (i == (int)a.size()) { out.push_back(cur); return; } // push_back copies cur
cur.push_back(a[i]);
pick(a, i + 1, cur, out);
cur.pop_back();
pick(a, i + 1, cur, out);
}
void build(const vector<int>& a, vector<bool>& used, vector<int>& cur, vector<vector<int>>& out) {
if (cur.size() == a.size()) { out.push_back(cur); return; }
for (int i = 0; i < (int)a.size(); i++) {
if (used[i]) continue;
used[i] = true; cur.push_back(a[i]);
build(a, used, cur, out);
cur.pop_back(); used[i] = false;
}
}
void print(const vector<vector<int>>& v) {
cout << "[";
for (size_t k = 0; k < v.size(); k++) {
cout << (k ? ", " : "") << "[";
for (size_t j = 0; j < v[k].size(); j++) cout << (j ? ", " : "") << v[k][j];
cout << "]";
}
cout << "]\n";
}
int main() {
vector<int> a = {1, 2, 3}, cur;
vector<vector<int>> subs, perms;
pick(a, 0, cur, subs);
vector<bool> used(a.size(), false);
build(a, used, cur, perms);
print(subs);
print(perms);
}
Output:
[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
In C++, out.push_back(cur) already copies the vector, so the "missing copy" bug from Java can't happen here.
The same solution in Python
def subsets(a):
out, cur = [], []
def pick(i):
if i == len(a):
out.append(cur[:]) # a copy, not cur itself
return
cur.append(a[i]) # choose
pick(i + 1) # explore
cur.pop() # un-choose
pick(i + 1) # skip a[i]
pick(0)
return out
def perms(a):
out, cur, used = [], [], [False] * len(a)
def build():
if len(cur) == len(a):
out.append(cur[:])
return
for i in range(len(a)):
if used[i]:
continue
used[i] = True; cur.append(a[i])
build()
cur.pop(); used[i] = False
build()
return out
print(subsets([1, 2, 3]))
print(perms([1, 2, 3]))
Output:
[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
In Python, out.append(cur) would store a reference (the same bug as Java); cur[:] makes the copy. The standard library also has itertools.permutations and itertools.combinations, but interviews expect you to write the backtracking yourself.
Three real bugs
Bug 1: no un-choose (the cur.remove(...) line is missing)
cur.add(a[i]);
pick(a, i + 1, cur, out);
pick(a, i + 1, cur, out);
Output for [1, 2, 3]:
[[1, 2, 3], [1, 2, 3], [1, 2, 3, 3], [1, 2, 3, 3], [1, 2, 3, 3, 2, 3], [1, 2, 3, 3, 2, 3], [1, 2, 3, 3, 2, 3, 3], [1, 2, 3, 3, 2, 3, 3]]
Every choice stays in cur forever, so the "skip" branch skips nothing and the lists only grow. Whatever you add before exploring, remove after.
Bug 2: out.add(cur) without a copy
Output for [1, 2, 3]:
[[], [], [], [], [], [], [], []]
out holds 8 references to one list object. By the end every choice has been un-chosen, so that list is empty, and you see it 8 times. Always out.add(new ArrayList<>(cur)).
Bug 3: used[i] never reset to false
Output for perms([1, 2, 3]):
[[1, 2, 3]]
After the first leaf every number stays marked as used, so no other branch can start. Un-choose means undoing everything you changed: the list and the flag.
A fourth trap: cur.remove(a[i])
On a List<Integer>, remove(int) removes by index, not by value:
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 3 out of bounds for length 3
With other values it can silently remove the wrong element. Use cur.remove(cur.size() - 1) (or cur.remove(Integer.valueOf(x)) if you really mean the value).
Complexity
| Approach | Time | Extra space | n = 10 |
|---|---|---|---|
| Nested loops | O(2ⁿ) | O(1) | needs 10 loops typed by hand |
| Odometer over nⁿ sequences (orders) | O(n · nⁿ) | O(n) | Time Limit Exceeded |
| Backtracking subsets (take / skip) | O(n · 2ⁿ) | O(n) + output | 1,024 subsets, instant |
Backtracking permutations (used[]) |
O(n · n!) | O(n) + output | 36 lakh orders in ~60 ms (counting) |
There are 2ⁿ subsets and n! permutations, and copying each answer into the output costs up to n, so you cannot do better than the size of the output. The recursion is n levels deep, so the extra space (call stack + cur + used) is O(n), not counting the output itself.
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
No cur.remove(...) after exploring |
[[1, 2, 3], [1, 2, 3], [1, 2, 3, 3], ...] |
choices are never undone | remove the last element after the call |
out.add(cur) |
[[], [], [], [], [], [], [], []] |
8 references to one list | out.add(new ArrayList<>(cur)) |
No used[i] = false |
[[1, 2, 3]] |
numbers stay used forever | reset the flag after the call |
cur.remove(a[i]) on a List<Integer> |
IndexOutOfBoundsException: Index 3 out of bounds for length 3 |
remove(int) removes by index |
cur.remove(cur.size() - 1) |
| No base case / wrong base case | StackOverflowError or missing answers |
the recursion never stops, or stops early | stop when i == a.length (subsets) or cur.size() == n (permutations) |
| One loop per item | still 8 thalis for 4 extras |
loop depth fixed at compile time | recursion |
| Odometer over all nⁿ sequences | TLE at n = 10 | builds invalid orders first | backtracking with used[] |
Mini project: the thali menu card
Print every thali with its price. Base thali Rs 120, papad Rs 10, raita Rs 20, sweet Rs 30. Pass the running total down the recursion:
static void menu(String[] name, int[] price, int i, List<String> cur, int total) {
if (i == name.length) {
System.out.println((cur.isEmpty() ? "plain thali" : String.join(" + ", cur)) + " = Rs " + total);
return;
}
cur.add(name[i]);
menu(name, price, i + 1, cur, total + price[i]);
cur.remove(cur.size() - 1);
menu(name, price, i + 1, cur, total);
}
menu(new String[]{"papad", "raita", "sweet"}, new int[]{10, 20, 30}, 0, new ArrayList<>(), 120) prints:
papad + raita + sweet = Rs 180
papad + raita = Rs 150
papad + sweet = Rs 160
papad = Rs 130
raita + sweet = Rs 170
raita = Rs 140
sweet = Rs 150
plain thali = Rs 120
Extension: print only the thalis under a budget, and stop exploring a branch as soon as the total goes over it (that's pruning, next episode).
Practice
- Subsets II:
[1, 2, 2]without duplicate subsets (LeetCode 90).
Solution
Sort, then build subsets with a loop that picks the next element; at the same level, skip a number equal to the one before it.
static void dup(int[] a, int start, List<Integer> cur, List<List<Integer>> out) {
out.add(new ArrayList<>(cur));
for (int i = start; i < a.length; i++) {
if (i > start && a[i] == a[i - 1]) continue;
cur.add(a[i]);
dup(a, i + 1, cur, out);
cur.remove(cur.size() - 1);
}
}
static List<List<Integer>> subsetsWithDup(int[] a) {
Arrays.sort(a);
List<List<Integer>> out = new ArrayList<>();
dup(a, 0, new ArrayList<>(), out);
return out;
}
[1, 2, 2] → [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]].
- Permutations II:
[1, 1, 2]without duplicate orders (LeetCode 47).
Solution
Sort; skip a[i] if it equals a[i - 1] and a[i - 1] is not used (so equal numbers are always placed in the same order).
static void build2(int[] a, boolean[] used, List<Integer> cur, List<List<Integer>> out) {
if (cur.size() == a.length) { out.add(new ArrayList<>(cur)); return; }
for (int i = 0; i < a.length; i++) {
if (used[i]) continue;
if (i > 0 && a[i] == a[i - 1] && !used[i - 1]) continue;
used[i] = true; cur.add(a[i]);
build2(a, used, cur, out);
cur.remove(cur.size() - 1); used[i] = false;
}
}
[1, 1, 2] (sorted first) → [[1, 1, 2], [1, 2, 1], [2, 1, 1]].
- All subsets of size k (combinations) (LeetCode 77): choose k numbers from 1..n.
Solution
static void comb(int n, int k, int start, List<Integer> cur, List<List<Integer>> out) {
if (cur.size() == k) { out.add(new ArrayList<>(cur)); return; }
for (int x = start; x <= n; x++) {
cur.add(x);
comb(n, k, x + 1, cur, out);
cur.remove(cur.size() - 1);
}
}
n = 4, k = 2 → [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]].
- Letter case permutation:
a1b→a1b, a1B, A1b, A1B(LeetCode 784).
Solution
Each letter is a take-or-skip decision: keep its case, or flip it (and flip it back after exploring).
static void cases(char[] s, int i, List<String> out) {
if (i == s.length) { out.add(new String(s)); return; }
cases(s, i + 1, out);
if (Character.isLetter(s[i])) {
s[i] = Character.isLowerCase(s[i]) ? Character.toUpperCase(s[i]) : Character.toLowerCase(s[i]);
cases(s, i + 1, out);
s[i] = Character.isLowerCase(s[i]) ? Character.toUpperCase(s[i]) : Character.toLowerCase(s[i]);
}
}
"a1b" → [a1b, a1B, A1b, A1B].
Quick quiz
System.out.println(subsets(new int[]{4, 5}));
System.out.println(perms(new int[]{4, 5}));
[[4, 5], [4], [5], []]and[[4, 5], [5, 4]][[], [4], [5], [4, 5]]and[[4, 5]][[4, 5], [4], [5], []]and[[4, 5], [4, 5]][[4], [5]]and[[4, 5], [5, 4]]
Answer
The first one. Subsets take before skip: [4, 5], [4], [5], []. Permutations put 4 in the first seat, then 5: [4, 5], [5, 4]. (Real output: [[4, 5], [4], [5], []] then [[4, 5], [5, 4]].)
Interview questions
- What is backtracking? Building a solution one choice at a time, recursing, and undoing the last choice when you come back, so you can try the next one. It walks a decision tree depth-first with a single shared state.
- How many subsets and permutations does an array of n distinct elements have? 2ⁿ subsets, n! permutations.
- Time complexity of generating all subsets / permutations? O(n·2ⁿ) and O(n·n!): the number of answers times the cost of copying each one.
- Why
new ArrayList<>(cur)and notcur?curis one object that keeps changing; adding it stores a reference, so every saved answer ends up the same (empty) list. - Can you generate subsets without recursion? Yes: count a bitmask from 0 to 2ⁿ - 1; bit j set means "take item j". Same O(n·2ⁿ).
- How do you handle duplicates in the input? Sort, then at the same level of the tree skip a value equal to the previous one (Subsets II, Permutations II).
- What is the space complexity? O(n) for the recursion depth,
curandused, plus the output. - What's the difference between a subset, a combination and a permutation? A subset is any selection; a combination is a selection of a fixed size k; a permutation is an ordering where order matters.
Glossary
| Term | Meaning |
|---|---|
| Subset | Any selection of the items (including none or all); order doesn't matter |
| Power set | The set of all subsets: 2ⁿ of them |
| Permutation | An ordering of all the items; order matters; n! of them |
| Combination | A selection of exactly k items, order doesn't matter |
| Factorial (n!) | n × (n - 1) × … × 1; 3! = 6, 10! = 36,28,800 |
| Recursion | A function that calls itself on a smaller version of the same problem |
| Base case | The condition where the recursion stops (all items decided) |
| Decision tree / recursion tree | A picture of the calls: one level per decision, one leaf per complete answer |
| Leaf | A node of the tree with no children: here, one complete subset or order |
| Backtracking | Choose → explore → un-choose: undo the last choice and try the next one |
cur |
The current partial answer, shared by every call, growing and shrinking |
used[] |
A boolean array marking which items are already placed in the permutation |
| Reference | A variable that points at an object; two references can point at the same list |
| Pruning | Cutting off a branch of the tree early because it can't lead to an answer (next episode) |
| Time Limit Exceeded (TLE) | Too slow for the judge's limit (8 s in the SyntaxPilot compiler) |
StackOverflowError |
Java's error when recursion goes too deep (often a missing base case) |
Summary
- Nested loops can't grow with n; the odometer can, but builds nⁿ sequences to keep n! and times out at n = 10.
- Recursion walks a decision tree as deep as n. At each level: choose → explore → un-choose. Save a copy at every leaf; reset every flag you set.
- Subsets: take or skip each item, O(n·2ⁿ). Permutations: fill seat by seat with
used[], O(n·n!). Extra space O(n) plus the output.
Next episode: Combination sum.