Generate All Permutations Using Bitmask DP

🎯

Generate All Permutations Using Bitmask DP

hardBIT_MANIPULATIONGoogleAmazon

Imagine you are organizing a tournament where each player must play in every possible order. You want to generate all possible sequences efficiently using bit operations.

💡 This problem involves generating all permutations of a set using bitmasking to track which elements have been used. Beginners often struggle because permutations are usually generated with recursion and arrays, but here we use bits to represent visited elements, which requires understanding bitwise operations and recursion together.

📋

Problem Statement

Given an integer n, generate all permutations of the numbers from 0 to n-1 using bitmasking to track visited elements. Output all permutations as lists of integers. Input: integer n. Output: list of all permutations, each permutation is a list of integers from 0 to n-1 with no repeats.

1 ≤ n ≤ 10Output size grows factorially, so n is limited to small valuesUse bitmasking to track visited elements efficiently

💡

Example

Input"3"

Output[[0,1,2],[0,2,1],[1,0,2],[1,2,0],[2,0,1],[2,1,0]]

All permutations of [0,1,2] are generated using bitmask to track which elements are used.

• n = 1 → [[0]]
• n = 0 → [] (no permutations)
• n = 2 → [[0,1],[1,0]]
• n = 10 → large output, test performance and correctness

⚠️

Common Mistakes

Not using bitmask to track visited elements

Code uses arrays and misses optimization opportunities

✅ Use integer bitmask and bit operations to track visited

Forgetting to backtrack visited state after recursion

Incorrect permutations or infinite recursion

✅ Reset visited bit or boolean after recursive call

Not memoizing visited states in recursive bitmask DP

Excessive recomputation, slow runtime

✅ Store visited masks in memo set or dictionary

Using iterative DP but not initializing dp[0] correctly

No base case leads to empty results

✅ Set dp[0] = [[]] to represent empty permutation

Trying to generate permutations for large n (e.g., n=20)

Program runs out of memory or time

✅ Limit input size or use counting methods instead of generation

🧠

Brute Force (Pure Recursion with Visited Array)

💡 This approach uses simple recursion and an array to track visited elements. It is the most intuitive way to generate permutations but does not use bitmasking. It helps beginners understand the problem before optimizing.

Intuition

Try every number at each position if it is not visited, recurse until all positions are filled.

Algorithm

1. Initialize a visited boolean array of size n to false.
2. Recursively build permutations by choosing unvisited elements.
3. Mark chosen element as visited and add to current permutation.
4. When permutation length equals n, add it to results.

💡 The recursion tree explores all choices at each position, which is easy to visualize but inefficient for large n.

</>

Code

def generate_permutations(n):
    result = []
    visited = [False] * n
    def backtrack(path):
        if len(path) == n:
            result.append(path[:])
            return
        for i in range(n):
            if not visited[i]:
                visited[i] = True
                path.append(i)
                backtrack(path)
                path.pop()
                visited[i] = False
    backtrack([])
    return result

# Driver code
if __name__ == '__main__':
    n = 3
    perms = generate_permutations(n)
    print(perms)

Line Notes

visited = [False] * nInitialize visited array to track which elements are used

def backtrack(path):Define recursive function to build permutations

if len(path) == n:Base case: permutation complete, add to results

for i in range(n):Try every element to add if not visited

import java.util.*;
public class Main {
    public static List<List<Integer>> generatePermutations(int n) {
        List<List<Integer>> result = new ArrayList<>();
        boolean[] visited = new boolean[n];
        backtrack(n, new ArrayList<>(), visited, result);
        return result;
    }
    private static void backtrack(int n, List<Integer> path, boolean[] visited, List<List<Integer>> result) {
        if (path.size() == n) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                path.add(i);
                backtrack(n, path, visited, result);
                path.remove(path.size() - 1);
                visited[i] = false;
            }
        }
    }
    public static void main(String[] args) {
        int n = 3;
        List<List<Integer>> perms = generatePermutations(n);
        System.out.println(perms);
    }
}

Line Notes

boolean[] visited = new boolean[n];Track visited elements with boolean array

if (path.size() == n)Check if permutation is complete

for (int i = 0; i < n; i++)Try each element if not visited

visited[i] = true;Mark element as visited before recursion

#include <iostream>
#include <vector>
using namespace std;

void backtrack(int n, vector<int>& path, vector<bool>& visited, vector<vector<int>>& result) {
    if (path.size() == n) {
        result.push_back(path);
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            visited[i] = true;
            path.push_back(i);
            backtrack(n, path, visited, result);
            path.pop_back();
            visited[i] = false;
        }
    }
}

vector<vector<int>> generatePermutations(int n) {
    vector<vector<int>> result;
    vector<int> path;
    vector<bool> visited(n, false);
    backtrack(n, path, visited, result);
    return result;
}

int main() {
    int n = 3;
    vector<vector<int>> perms = generatePermutations(n);
    for (auto& perm : perms) {
        for (int x : perm) cout << x << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

vector<bool> visited(n, false);Boolean vector to track visited elements

if (path.size() == n)Base case: permutation complete

for (int i = 0; i < n; i++)Try each element if not visited

visited[i] = true;Mark element visited before recursive call

function generatePermutations(n) {
    const result = [];
    const visited = new Array(n).fill(false);
    function backtrack(path) {
        if (path.length === n) {
            result.push([...path]);
            return;
        }
        for (let i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                path.push(i);
                backtrack(path);
                path.pop();
                visited[i] = false;
            }
        }
    }
    backtrack([]);
    return result;
}

// Test
console.log(generatePermutations(3));

Line Notes

const visited = new Array(n).fill(false);Initialize visited array to track usage

if (path.length === n)Check if permutation is complete

for (let i = 0; i < n; i++)Try each element if not visited

visited[i] = true;Mark element visited before recursion

⏱

Complexity

TimeO(n!)

SpaceO(n) for recursion stack + O(n!) for output

We generate all n! permutations, each of length n, so time and output space are factorial in n. The recursion stack uses O(n) space.

💡 For n=3, 3! = 6 permutations, which is manageable. For n=10, 10! = 3,628,800 permutations, which is huge and impractical.

Interview Verdict: Accepted but inefficient for large n

This approach is easy to understand and implement but becomes too slow for larger inputs due to factorial growth.

🧠

Bitmask DP with Recursion and Memoization

💡 This approach uses bitmasking to represent visited elements instead of a boolean array, and memoizes intermediate results to avoid recomputation. It introduces bit operations to track state efficiently.

Intuition

Use an integer bitmask where each bit represents whether an element is used. Recursively build permutations by choosing elements whose bit is not set. Memoize results for each bitmask state.

Algorithm

1. Represent visited elements as bits in an integer mask.
2. Recursively try all elements whose bit is not set in mask.
3. Set bit for chosen element and recurse.
4. Memoize results for each mask to avoid recomputation.

💡 Bitmasking compresses visited info into an integer, making state management and memoization efficient.

</>

Code

def generate_permutations_bitmask(n):
    memo = {}
    def backtrack(mask):
        if mask == (1 << n) - 1:
            return [[]]
        if mask in memo:
            return memo[mask]
        result = []
        for i in range(n):
            if not (mask & (1 << i)):
                for perm in backtrack(mask | (1 << i)):
                    result.append([i] + perm)
        memo[mask] = result
        return result

# Driver code
if __name__ == '__main__':
    n = 3
    perms = generate_permutations_bitmask(n)
    print(perms)

Line Notes

memo = {}Store visited states and their permutations to avoid recomputation

if mask == (1 << n) - 1:All elements visited when mask has all bits set; return list with empty permutation

if mask in memo:Return memoized permutations for this mask to avoid repeated work

for i in range(n):Try each element not visited in current mask

import java.util.*;
public class Main {
    static Map<Integer, List<List<Integer>>> memo;
    public static List<List<Integer>> backtrack(int n, int mask) {
        if (mask == (1 << n) - 1) {
            List<List<Integer>> base = new ArrayList<>();
            base.add(new ArrayList<>());
            return base;
        }
        if (memo.containsKey(mask)) return memo.get(mask);
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) == 0) {
                for (List<Integer> perm : backtrack(n, mask | (1 << i))) {
                    List<Integer> newPerm = new ArrayList<>();
                    newPerm.add(i);
                    newPerm.addAll(perm);
                    result.add(newPerm);
                }
            }
        }
        memo.put(mask, result);
        return result;
    }
    public static List<List<Integer>> generatePermutationsBitmask(int n) {
        memo = new HashMap<>();
        return backtrack(n, 0);
    }
    public static void main(String[] args) {
        int n = 3;
        List<List<Integer>> perms = generatePermutationsBitmask(n);
        System.out.println(perms);
    }
}

Line Notes

static Map<Integer, List<List<Integer>>> memo;Memoize visited bitmask states and their permutations

if (mask == (1 << n) - 1)Base case: all elements visited, return list with empty permutation

if (memo.containsKey(mask))Return memoized permutations for this mask

for (int i = 0; i < n; i++)Try each element not visited in mask

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

unordered_map<int, vector<vector<int>>> memo;

vector<vector<int>> backtrack(int n, int mask) {
    if (mask == (1 << n) - 1) {
        return {{};}
    }
    if (memo.count(mask)) return memo[mask];
    vector<vector<int>> result;
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) == 0) {
            for (auto& perm : backtrack(n, mask | (1 << i))) {
                vector<int> newPerm = {i};
                newPerm.insert(newPerm.end(), perm.begin(), perm.end());
                result.push_back(newPerm);
            }
        }
    }
    memo[mask] = result;
    return result;
}

vector<vector<int>> generatePermutationsBitmask(int n) {
    memo.clear();
    return backtrack(n, 0);
}

int main() {
    int n = 3;
    auto perms = generatePermutationsBitmask(n);
    for (auto& perm : perms) {
        for (int x : perm) cout << x << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

unordered_map<int, vector<vector<int>>> memo;Memoize visited bitmask states and their permutations

if (mask == (1 << n) - 1)Base case: all elements visited, return list with empty permutation

if (memo.count(mask))Return memoized permutations for this mask

for (int i = 0; i < n; i++)Try each element not visited in mask

function generatePermutationsBitmask(n) {
    const memo = new Map();
    function backtrack(mask) {
        if (mask === (1 << n) - 1) return [[]];
        if (memo.has(mask)) return memo.get(mask);
        const result = [];
        for (let i = 0; i < n; i++) {
            if ((mask & (1 << i)) === 0) {
                for (const perm of backtrack(mask | (1 << i))) {
                    result.push([i, ...perm]);
                }
            }
        }
        memo.set(mask, result);
        return result;
    }
    return backtrack(0);
}

// Test
console.log(generatePermutationsBitmask(3));

Line Notes

const memo = new Map();Memoize visited bitmask states and their permutations

if (mask === (1 << n) - 1)Base case: all elements visited, return list with empty permutation

if (memo.has(mask))Return memoized permutations for this mask

for (let i = 0; i < n; i++)Try each element not visited in mask

⏱

Complexity

TimeO(n * n!)

SpaceO(n * n!) for recursion and memo

Memoization stores all permutations for each visited mask. There are n! permutations total, and each state tries up to n elements, so time and space are O(n * n!).

💡 Memoization reduces repeated work but factorial growth remains, so this is still expensive for large n.

Interview Verdict: Accepted and more efficient than brute force

Using bitmask and memoization is a common optimization that improves efficiency and is expected in interviews.

🧠

Bitmask DP with Iterative Tabulation (Bottom-Up)

💡 This approach uses bottom-up DP with bitmask states to iteratively build permutations without recursion. It is optimal for small n and demonstrates mastery of bitmask DP.

Intuition

Use a DP array where dp[mask] stores all partial permutations for visited set mask. Build dp states by adding one element at a time to smaller masks.

Algorithm

1. Initialize dp array of size 2^n with empty lists.
2. Set dp[0] = [[]], representing empty permutation.
3. For each mask from 0 to 2^n - 1, add each unused element i to permutations in dp[mask] to form dp[mask | (1 << i)].
4. Return dp[(1 << n) - 1] containing all full permutations.

💡 This approach explicitly stores all partial permutations for each visited state, building up to full permutations.

</>

Code

def generate_permutations_iterative(n):
    dp = [[] for _ in range(1 << n)]
    dp[0] = [[]]
    for mask in range(1 << n):
        for i in range(n):
            if not (mask & (1 << i)):
                for perm in dp[mask]:
                    dp[mask | (1 << i)].append(perm + [i])
    return dp[(1 << n) - 1]

# Driver code
if __name__ == '__main__':
    n = 3
    perms = generate_permutations_iterative(n)
    print(perms)

Line Notes

dp = [[] for _ in range(1 << n)]Initialize DP array for all bitmask states

dp[0] = [[]]Empty permutation for empty visited set

if not (mask & (1 << i))Check if element i is unused in current mask

dp[mask | (1 << i)].append(perm + [i])Add element i to partial permutations to form new state

import java.util.*;
public class Main {
    public static List<List<Integer>> generatePermutationsIterative(int n) {
        List<List<List<Integer>>> dp = new ArrayList<>();
        for (int i = 0; i < (1 << n); i++) dp.add(new ArrayList<>());
        dp.get(0).add(new ArrayList<>());
        for (int mask = 0; mask < (1 << n); mask++) {
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) == 0) {
                    for (List<Integer> perm : dp.get(mask)) {
                        List<Integer> newPerm = new ArrayList<>(perm);
                        newPerm.add(i);
                        dp.get(mask | (1 << i)).add(newPerm);
                    }
                }
            }
        }
        return dp.get((1 << n) - 1);
    }
    public static void main(String[] args) {
        int n = 3;
        List<List<Integer>> perms = generatePermutationsIterative(n);
        System.out.println(perms);
    }
}

Line Notes

List<List<List<Integer>>> dp = new ArrayList<>();DP array stores lists of permutations for each mask

dp.get(0).add(new ArrayList<>());Empty permutation for empty mask

if ((mask & (1 << i)) == 0)Check if element i unused in mask

dp.get(mask | (1 << i)).add(newPerm);Add new permutation with element i included

#include <iostream>
#include <vector>
using namespace std;

vector<vector<vector<int>>> generatePermutationsIterative(int n) {
    int size = 1 << n;
    vector<vector<vector<int>>> dp(size);
    dp[0].push_back({});
    for (int mask = 0; mask < size; mask++) {
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) == 0) {
                for (auto& perm : dp[mask]) {
                    vector<int> newPerm = perm;
                    newPerm.push_back(i);
                    dp[mask | (1 << i)].push_back(newPerm);
                }
            }
        }
    }
    return dp[size - 1];
}

int main() {
    int n = 3;
    auto perms = generatePermutationsIterative(n);
    for (auto& perm : perms) {
        for (int x : perm) cout << x << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

vector<vector<vector<int>>> dp(size);DP array stores all partial permutations for each mask

dp[0].push_back({});Empty permutation for empty mask

if ((mask & (1 << i)) == 0)Check if element i unused in mask

dp[mask | (1 << i)].push_back(newPerm);Add new permutation with element i included

function generatePermutationsIterative(n) {
    const size = 1 << n;
    const dp = Array.from({ length: size }, () => []);
    dp[0].push([]);
    for (let mask = 0; mask < size; mask++) {
        for (let i = 0; i < n; i++) {
            if ((mask & (1 << i)) === 0) {
                for (const perm of dp[mask]) {
                    dp[mask | (1 << i)].push([...perm, i]);
                }
            }
        }
    }
    return dp[size - 1];
}

// Test
console.log(generatePermutationsIterative(3));

Line Notes

const dp = Array.from({ length: size }, () => []);Initialize DP array for all bitmask states

dp[0].push([]);Empty permutation for empty visited set

if ((mask & (1 << i)) === 0)Check if element i is unused

dp[mask | (1 << i)].push([...perm, i]);Add element i to partial permutations

⏱

Complexity

TimeO(n * n!)

SpaceO(n * n!) for DP storage

We build all permutations iteratively. Each of the 2^n states stores partial permutations, total permutations are n! and each is length n.

💡 This approach is optimal for small n but memory intensive due to storing all partial permutations explicitly.

Interview Verdict: Accepted and optimal for small n

Iterative bitmask DP is a powerful technique to avoid recursion and is preferred when recursion depth or overhead is a concern.

📊

All Approaches - One-Glance Tradeoffs

💡 For interviews, coding the bitmask DP with memoization (Approach 2) is usually best. Brute force is good to explain, iterative DP is optimal but verbose.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n!)	O(n) recursion + O(n!) output	Yes (deep recursion)	Yes	Mention only - never code for large n
2. Bitmask DP with Memoization	O(n * n!)	O(n * n!) memo + output	Less (memo prunes)	Yes	Code this for optimal balance
3. Iterative Bitmask DP	O(n * n!)	O(n * n!) DP storage	No	Yes	Good for demonstrating DP mastery, but verbose

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start with brute force to clarify the problem, then optimize step-by-step. Practice coding all approaches and explaining tradeoffs.

How to Present

Step 1: Clarify problem and constraints.Step 2: Describe brute force recursion with visited array.Step 3: Introduce bitmasking to track visited elements.Step 4: Add memoization to prune repeated states.Step 5: Optionally implement iterative DP for optimal solution.Step 6: Discuss time and space complexity and edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of permutations, bitmasking, recursion, memoization, and DP. They want to see clear thinking, correctness, and optimization skills.

Common Follow-ups

• How to count permutations without generating them? → Use factorial or DP counting.
• Can this approach handle duplicates? → Modify to skip duplicates or use frequency counts.

💡 Follow-ups test your ability to adapt the solution to counting problems or handle duplicates, common in permutation questions.

🔍

Pattern Recognition

When to Use

1) Need to generate or count permutations or subsets; 2) State can be represented as visited elements; 3) Bitmasking can compress visited state; 4) Overlapping subproblems suggest memoization or DP.

Signature Phrases

generate all permutationsvisited state represented as bitsbitmask DP

NOT This Pattern When

Problems that require greedy or sorting but do not track visited states with bitmask.

Similar Problems

Permutations II - handle duplicates with bitmask and frequency countsCount All Permutations - count permutations using DP with bitmaskSubset Generation with Bitmask - generate subsets using bitmask states

Practice

1. Given the following Python code to generate Gray code sequence, what is the output of grayCode(2)?

easy

A. [1, 0, 3, 2]

B. [0, 1, 2, 3]

C. [0, 1, 3, 2]

D. [0, 2, 3, 1]

Solution

1. Step 1: Compute values for i in range(4)

   For i=0: 0 ^ (0>>1)=0; i=1: 1 ^ (0)=1; i=2: 2 ^ (1)=2^1=3; i=3: 3 ^ (1)=3^1=2

2. Step 2: Collect results in list

   The sequence is [0, 1, 3, 2], which matches the Gray code property.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Manual XOR calculation confirms the sequence [0,1,3,2] [OK]

Hint: XOR with right-shifted index generates Gray code directly [OK]

Common Mistakes:

• Confusing the order of XOR and shift
• Off-by-one errors in range leading to missing or extra elements
• Misinterpreting the output as binary numbers instead of integers

2. Given the following Python function for UTF-8 validation, what is the value of the variable remaining after processing the second byte in the input [197, 130, 1]?

def validUtf8(data):
    remaining = 0
    for byte in data:
        if remaining == 0:
            if (byte >> 5) == 0b110:
                remaining = 1
            elif (byte >> 4) == 0b1110:
                remaining = 2
            elif (byte >> 3) == 0b11110:
                remaining = 3
            elif (byte >> 7) == 0:
                remaining = 0
            else:
                return False
        else:
            if (byte >> 6) != 0b10:
                return False
            remaining -= 1
    return remaining == 0

easy

A. 2

B. 0

C. 1

D. False (function returns early)

Solution

1. Step 1: Trace first byte (197)

   197 in binary is 11000101. (197 >> 5) == 0b110, so remaining is set to 1.

2. Step 2: Trace second byte (130)

   Since remaining is 1, check if (130 >> 6) == 0b10. 130 in binary is 10000010, so condition holds and remaining is decremented to 0.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Remaining after second byte is 1 -> decremented to 0 after processing second byte [OK]

Hint: Check bit shifts and decrement continuation counter correctly [OK]

Common Mistakes:

• Off-by-one decrement of remaining
• Misinterpreting bit shifts for continuation bytes

3. The following code attempts to find the maximum product of word lengths with no common letters. Which line contains a subtle bug that can cause incorrect results or inefficiency?

medium

A. Line 18: Checking bitmask overlap with bitwise AND

B. Line 10: Sorting masks by length in descending order

C. Line 14: Breaking outer loop when max product cannot improve

D. Line 6: Incorrect bit shift by adding 1 to character index

Solution

1. Step 1: Identify bitmask construction

   Line 6 shifts bits by (ord(ch) - ord('a') + 1), which incorrectly shifts by 1 extra, causing wrong bitmask representation.

2. Step 2: Impact of incorrect bitmask

   This causes overlap checks to fail or miss common letters, leading to incorrect max product or missed pruning opportunities.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bitmask must shift by (ord(ch) - ord('a')) exactly [OK]

Hint: Bit shift must match character index exactly [OK]

Common Mistakes:

• Off-by-one bit shifting in bitmask
• Not pruning pairs after sorting
• Incorrect overlap check logic

4. Identify the bug in the following trie-based maximum XOR code snippet:

medium

A. Line with 'node = node.children[bit]' does not check if 'bit' exists in children.

B. Line with 'if bit not in node.children:' should check for toggled_bit instead.

C. Line with 'max_xor |= (1 << i)' should be outside the if condition.

D. Line with 'node = self.root' should be inside the for loop.

Solution

1. Step 1: Analyze traversal in findMaxXor

   When toggled_bit is not found, code moves to node.children[bit] without checking if bit exists, risking KeyError.

2. Step 2: Identify missing null check

   Should use node.children.get(bit) or check existence before accessing to avoid runtime error.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing check causes crash on inputs missing bit child [OK]

Hint: Always check child existence before traversal [OK]

Common Mistakes:

• Assuming child always exists
• Confusing toggled_bit check
• Misplacing max_xor update

5. If the input number n can be negative or zero, and you want to check if its absolute value is a power of four, which modification to the optimal logarithm-based approach is correct?

hard

A. Remove the check for n <= 0 and directly compute log2(n)/2

B. Add a check to return False if n is zero or negative before applying logarithm on abs(n)

C. Use the brute force iterative division approach instead, as logarithm fails for negative inputs

D. Take the absolute value of n before the logarithm check and keep the rest unchanged

Solution

1. Step 1: Consider input domain

   Since n can be zero or negative, these are not powers of four, so must return False immediately.

2. Step 2: Apply logarithm check on absolute value

   After filtering invalid inputs, apply logarithm on abs(n) to check power of four.

3. Step 3: Finalize correct approach

   Adding a check to return False for zero or negative inputs before log check ensures correctness and avoids math domain errors.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Zero and negatives are filtered out before log check on abs(n) [OK]

Hint: Filter invalid inputs before log check on abs(n)

Common Mistakes:

• Removing input validation
• Applying log on negative numbers causing errors