Generate All Permutations Using Bitmask DP

▶

Steps

setup

Initialize dp array

Create the dp array with 2^3=8 slots, each initially empty. Set dp[0] to contain the empty permutation.

💡 This sets up the structure to store permutations for every subset of elements represented by bitmasks.

Line:

dp = [[] for _ in range(1 << n)]
dp[0] = [[]]

💡 dp[mask] will hold all permutations of elements included in mask; starting with empty set at dp[0].

traverse

Start iterating mask = 0

Begin with mask=0 (no elements chosen). We will try to add each element i=0,1,2 to this empty set.

💡 This step starts building permutations by adding elements to the empty set.

Line:

for mask in range(1 << n):
    # mask = 0 first iteration

💡 mask=0 means no elements are chosen yet; all elements are candidates to add.

compare

Check element i=0 unused in mask=0

Check if element 0 is unused in mask=0 by testing bit 0. Since bit 0 is 0, element 0 can be added.

💡 This check ensures we only add elements not already in the current permutation subset.

Line:

if not (mask & (1 << i)):
    # i=0, mask=0, bit 0 is 0

💡 Bit 0 unset means element 0 is free to add to current permutations.

insert

Add element 0 to mask=0 permutations

Add element 0 to all permutations in dp[0] (which is [[]]) and store in dp[1] (mask 0001).

💡 This step builds new permutations by including element 0.

Line:

dp[mask | (1 << i)].append(perm + [i])
# mask=0, i=0, dp[1].append([0])

💡 dp[1] now contains [[0]], permutations with element 0 included.

compare

Check element i=1 unused in mask=0

Check if element 1 is unused in mask=0 by testing bit 1. Bit 1 is 0, so element 1 can be added.

💡 We test each element to see if it can be added to current permutations.

Line:

if not (mask & (1 << i)):
    # i=1, mask=0, bit 1 is 0

💡 Bit 1 unset means element 1 is free to add.

insert

Add element 1 to mask=0 permutations

Add element 1 to all permutations in dp[0] (which is [[]]) and store in dp[2] (mask 0010).

💡 This expands dp[2] with permutations containing element 1.

Line:

dp[mask | (1 << i)].append(perm + [i])
# mask=0, i=1, dp[2].append([1])

💡 dp[2] now contains [[1]], permutations with element 1 included.

compare

Check element i=2 unused in mask=0

Check if element 2 is unused in mask=0 by testing bit 2. Bit 2 is 0, so element 2 can be added.

💡 Continuing to test all elements for addition.

Line:

if not (mask & (1 << i)):
    # i=2, mask=0, bit 2 is 0

💡 Bit 2 unset means element 2 is free to add.

insert

Add element 2 to mask=0 permutations

Add element 2 to all permutations in dp[0] (which is [[]]) and store in dp[4] (mask 0100).

💡 This adds permutations with element 2 included.

Line:

dp[mask | (1 << i)].append(perm + [i])
# mask=0, i=2, dp[4].append([2])

💡 dp[4] now contains [[2]], permutations with element 2 included.

traverse

Iterate mask=1 (0001) with element 0 included

Now process mask=1 where element 0 is included. We try to add unused elements 1 and 2.

💡 This step shows how permutations grow by adding elements to existing subsets.

Line:

for mask in range(1 << n):
    # mask=1 now

💡 Mask 1 means permutations with element 0 are ready to expand.

compare

Check element i=1 unused in mask=1

Check if element 1 is unused in mask=1 by testing bit 1. Bit 1 is 0, so element 1 can be added.

💡 We test which elements can be added to current mask.

Line:

if not (mask & (1 << i)):
    # i=1, mask=1, bit 1 is 0

💡 Bit 1 unset means element 1 is free to add.

insert

Add element 1 to mask=1 permutations

Add element 1 to all permutations in dp[1] (which is [[0]]) and store in dp[3] (mask 0011).

💡 This step extends permutations [0] by adding element 1.

Line:

dp[mask | (1 << i)].append(perm + [i])
# mask=1, i=1, dp[3].append([0,1])

💡 dp[3] now contains [[0,1]], permutations with elements 0 and 1 included.

compare

Check element i=2 unused in mask=1

Check if element 2 is unused in mask=1 by testing bit 2. Bit 2 is 0, so element 2 can be added.

💡 Continue checking elements for addition.

Line:

if not (mask & (1 << i)):
    # i=2, mask=1, bit 2 is 0

💡 Bit 2 unset means element 2 is free to add.

insert

Add element 2 to mask=1 permutations

Add element 2 to all permutations in dp[1] (which is [[0]]) and store in dp[5] (mask 0101).

💡 Extend permutations [0] by adding element 2.

Line:

dp[mask | (1 << i)].append(perm + [i])
# mask=1, i=2, dp[5].append([0,2])

💡 dp[5] now contains [[0,2]], permutations with elements 0 and 2 included.

traverse

Iterate mask=3 (0011) with elements 0 and 1 included

Process mask=3 where elements 0 and 1 are included. Try to add unused element 2.

💡 We build permutations with two elements by adding the last element.

Line:

for mask in range(1 << n):
    # mask=3 now

💡 Mask 3 means permutations with elements 0 and 1 are ready to expand.

compare

Check element i=2 unused in mask=3

Check if element 2 is unused in mask=3 by testing bit 2. Bit 2 is 0, so element 2 can be added.

💡 Only element 2 is left to add to complete permutations.

Line:

if not (mask & (1 << i)):
    # i=2, mask=3, bit 2 is 0

💡 Bit 2 unset means element 2 is free to add.

insert

Add element 2 to mask=3 permutations

Add element 2 to all permutations in dp[3] (which is [[0,1]]) and store in dp[7] (mask 0111).

💡 This completes permutations by adding the last element.

Line:

dp[mask | (1 << i)].append(perm + [i])
# mask=3, i=2, dp[7].append([0,1,2])

💡 dp[7] now contains [[0,1,2]], a full permutation of all elements.

traverse

Iterate mask=7 (0111) - full set

Mask=7 includes all elements 0,1,2. No more elements to add; dp[7] contains all full permutations.

💡 This is the final mask representing complete permutations.

Line:

return dp[(1 << n) - 1]
# dp[7] contains all permutations

💡 dp[7] holds all permutations of [0,1,2].

reconstruct

Final output: all permutations

Return dp[7], which contains all permutations: [[0,1,2],[0,2,1],[1,0,2],[1,2,0],[2,0,1],[2,1,0]].

💡 This final step shows the complete set of permutations generated by the algorithm.

Line:

return dp[(1 << n) - 1]

💡 The bitmask DP approach efficiently enumerates all permutations without recursion.

def generate_permutations_iterative(n):
    dp = [[] for _ in range(1 << n)]  # STEP 1 initialize dp
    dp[0] = [[]]  # STEP 1 empty permutation
    for mask in range(1 << n):  # STEP 2 traverse masks
        for i in range(n):  # STEP 3 check each element
            if not (mask & (1 << i)):  # STEP 3 check if element i unused
                for perm in dp[mask]:  # STEP 4 extend permutations
                    dp[mask | (1 << i)].append(perm + [i])  # STEP 4 add element i
    return dp[(1 << n) - 1]  # STEP 18 return full permutations

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

📊

Generate All Permutations Using Bitmask DP - Watch the Algorithm Execute, Step by Step

Watching each bitmask and permutation update helps you understand how bitmask DP efficiently enumerates permutations without recursion.

Initialize dp array

A

0

0

0

0

0

0

0

0

=0

B

💡 dp[0] initialized with empty permutation representing no elements chosen

Iterate mask=0

A

0

0

0

0

0

0

0

0

=0

B

💡 Starting with empty mask to add elements

Check bit 0 unused

A

0

0

0

0

0

0

0

0

=0

B

💡 Bit 0 is 0, element 0 unused

Add element 0

A

0

0

0

0

0

0

0

0

=0

B

💡 Mask 0001 means element 0 included

Check bit 1 unused

A

0

0

0

0

0

0

0

0

=0

B

💡 Bit 1 is 0, element 1 unused

Add element 1

A

0

0

0

0

0

0

0

0

=0

B

💡 Mask 0010 means element 1 included

Check bit 2 unused

A

0

0

0

0

0

0

0

0

=0

B

💡 Bit 2 is 0, element 2 unused

Add element 2

A

0

0

0

0

0

0

0

0

=0

B

💡 Mask 0100 means element 2 included

Iterate mask=1

A

0

1

=1

B

💡 Mask 0001 means element 0 included

Check bit 1 unused

A

0

1

=1

B

💡 Bit 1 is 0, element 1 unused

Add element 1

A

0

1

=1

B

💡 Mask 0011 means elements 0 and 1 included

Check bit 2 unused

A

0

1

=1

B

💡 Bit 2 is 0, element 2 unused

Add element 2

A

0

1

=1

B

💡 Mask 0101 means elements 0 and 2 included

Iterate mask=3

A

0

1

1

=3

B

💡 Mask 0011 means elements 0 and 1 included

Check bit 2 unused

A

0

1

1

=3

B

💡 Bit 2 is 0, element 2 unused

Add element 2

A

0

1

1

=3

B

💡 Mask 0111 means elements 0,1,2 included

Return all permutations

A

0

1

1

=7

B

────────────────

=

0

0

0

0

0

0

0

0

=7

💡 Mask 0111 means all elements included; dp[7] has all permutations

Return dp[7]

A

0

1

1

=7

B

────────────────

=

0

0

0

0

0

0

0

0

=7

💡 All permutations generated for full mask

Key Takeaways

✓ Bitmask DP efficiently tracks which elements are used in permutations using bits.

This insight is hard to see from code alone because bitmasks compactly represent subsets and their usage is implicit.

✓ Permutations are built incrementally by adding one unused element at a time to existing subsets.

Visualizing each mask and addition clarifies the dependency and growth of permutations.

✓ The final mask with all bits set contains all full permutations, showing the completeness of the approach.

Seeing the final mask and its permutations confirms the correctness and termination of the algorithm.

Practice

1. You need to determine if a given positive integer can be expressed as 4 raised to some integer power (i.e., n = 4^k for k ≥ 0). Which approach guarantees an optimal O(1) time solution without loops or recursion?

easy

A. Use logarithms to check if log base 4 of the number is an integer.

B. Iteratively divide the number by 4 until it becomes 1 or a non-divisible remainder is found.

C. Check if the number is a power of two and then verify if the set bit is in an even position using bitmasking.

D. Use dynamic programming to build up powers of four and compare with the number.

Solution

1. Step 1: Understand the problem requirement

   The problem asks for a constant-time check to determine if a number is a power of four, which means no loops or recursion.

2. Step 2: Evaluate approaches for O(1) time

   Using bitmasking to check if the number is a power of two and if the single set bit is in an even position is a known O(1) approach. Logarithm checks involve floating point operations and can have precision issues, so they are not guaranteed to be optimal or reliable in constant time. Iterative division and dynamic programming are not O(1).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bitmasking approach uses constant time bit operations [OK]

Hint: Bitmasking checks power of two and bit position in O(1)

Common Mistakes:

• Confusing power of two check with power of four
• Using loops despite O(1) requirement
• Relying on floating point logarithm checks which can be imprecise

2. Given the following code, what is the output of isPowerOfTwo(16) and isPowerOfTwo(218)?

def isPowerOfTwo(n: int) -> bool:
    if n <= 0:
        return False
    return bin(n).count('1') == 1

print(isPowerOfTwo(16))
print(isPowerOfTwo(218))

easy

A. True and False

B. False and True

C. True and True

D. False and False

Solution

1. Step 1: Trace isPowerOfTwo(16)

   16 in binary is 0b10000, which has exactly one '1' bit, so returns True.

2. Step 2: Trace isPowerOfTwo(218)

   218 in binary is 0b11011010, which has multiple '1' bits, so returns False.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Count of '1's in bin(16) == 1, in bin(218) > 1 [OK]

Hint: Power of two has exactly one set bit [OK]

Common Mistakes:

• Miscounting bits in binary representation
• Confusing zero or negative inputs

3. 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

4. What is the time complexity of the optimal bit reversal algorithm using divide and conquer masks on a fixed 32-bit integer?

medium

A. O(1) because the number of operations is fixed and independent of input size.

B. O(32) because each bit is processed individually in steps.

C. O(log n) where n is the number of bits, due to recursive bit swaps.

D. O(n) where n is the number of bits, since each bit must be moved at least once.

Solution

1. Step 1: Analyze algorithm steps

   The algorithm performs a sequence of bitwise operations that swap bits in stages, each stage halving the problem size.

2. Step 2: Determine complexity

   Since the algorithm performs log n stages (where n=32 bits), the time complexity is O(log n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Number of steps proportional to log n due to divide and conquer swaps [OK]

Hint: Divide and conquer bit swaps perform O(log n) steps [OK]

Common Mistakes:

• Assuming fixed bit width means O(1) for arbitrary n
• Confusing bit count with input size
• Thinking each bit is processed individually in a loop

5. If the input array can contain negative numbers, which modification is necessary for the optimal XOR and partition approach to correctly find the two unique numbers?

hard

A. No modification needed; the current approach works for negative numbers as is.

B. Use absolute values of numbers for XOR and partitioning to avoid sign issues.

C. Sort the array first to handle negative numbers before applying XOR partitioning.

D. Use set_bit = xor & (-xor) carefully, ensuring two's complement representation is handled correctly.

Solution

1. Step 1: Understand bitwise operations with negative numbers

   Negative numbers use two's complement; -xor computes two's complement correctly, so set_bit = xor & (-xor) works if implemented carefully.

2. Step 2: Identify necessary care

   Ensure language and environment handle negative bitwise operations properly; no need to sort or use absolute values.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct handling of two's complement is key for negative numbers [OK]

Hint: Two's complement handles negative bits; no sorting needed [OK]

Common Mistakes:

• Assuming XOR fails on negatives
• Sorting wastes time
• Using absolute values breaks uniqueness