Permutations

🎯

Permutations

mediumBACKTRACKINGAmazonMicrosoftGoogle

Imagine you are organizing a race and want to list all possible orders in which runners can finish. How many ways can you arrange them, and how do you generate each order?

💡 This problem asks for all possible orderings of a list of distinct elements. Beginners often struggle because the number of permutations grows factorially, and it's not obvious how to systematically generate all without repeats or missing any. Think of it like arranging runners in every possible finishing order, ensuring no order is missed or duplicated.

📋

Problem Statement

Given an array of distinct integers nums, return all possible permutations. You can return the answer in any order. Input: An array nums of distinct integers. Output: A list of lists, where each list is a unique permutation of nums.

1 ≤ nums.length ≤ 8All elements of nums are distinct integers

💡

Example

Input"[1,2,3]"

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

All 6 permutations of the array [1,2,3] are generated by swapping elements recursively.

• Empty array → [] (no permutations)
• Single element array → [[element]] (only one permutation)
• Array with two elements → two permutations swapping order
• Array with maximum length (8) → factorial(8) permutations (40320) to test performance

⚠️

Common Mistakes

Not backtracking properly (forgetting to unmark used or swap back)

Results contain duplicates or incomplete permutations

✅ Always undo changes after recursive calls to restore state

Modifying the input array without copying when adding to results

All results end up the same due to reference sharing

✅ Add a copy of the current permutation to results, not the original list

Using used array but not initializing or resetting it correctly

Some elements never get used or are reused incorrectly

✅ Initialize used array properly and reset used[i] after recursion

Trying to generate permutations for very large n without pruning

Code runs too long or crashes due to factorial explosion

✅ Recognize factorial growth and limit input size or optimize approach

Confusing permutations with combinations (order matters vs not)

Wrong number of results or missing orderings

✅ Remember permutations consider order, so generate all orderings

🧠

Brute Force (Pure Recursion with Used Array)

💡 This approach introduces the fundamental backtracking technique by trying every possible element at each position, using a boolean array to track which elements are already included. It helps beginners understand how to systematically explore all options without repetition.

Intuition

At each step, pick an unused element and add it to the current permutation until the permutation is complete. Then backtrack to try other options.

Algorithm

1. Initialize a boolean array to mark used elements.
2. Recursively build permutations by adding unused elements.
3. When the permutation length equals input length, add it to results.
4. Backtrack by unmarking the last used element and removing it from current permutation.

💡 The challenge is to understand how recursion and backtracking systematically explore all permutations without missing or repeating any.

</>

Code

from typing import List

def permute(nums: List[int]) -> List[List[int]]:
    res = []
    used = [False] * len(nums)
    path = []

    def backtrack():
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return res

# Driver code
if __name__ == '__main__':
    print(permute([1,2,3]))

Line Notes

used = [False] * len(nums)Track which elements are already included to avoid duplicates in the current permutation

if len(path) == len(nums)Base case: when current permutation is complete, add a copy to results

for i in range(len(nums))Try every element as the next candidate if not used

path.pop()Backtrack by removing last element to try other possibilities

backtrack()Start the recursive backtracking process from an empty path

used[i] = TrueMark element as used before recursive call to avoid reuse

used[i] = FalseUnmark element after recursion to allow other permutations

path.append(nums[i])Add current element to the path being built

import java.util.*;

public class Permutations {
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        List<Integer> path = new ArrayList<>();
        backtrack(nums, used, path, res);
        return res;
    }

    private static void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            path.add(nums[i]);
            backtrack(nums, used, path, res);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        System.out.println(permute(nums));
    }
}

Line Notes

boolean[] used = new boolean[nums.length]Boolean array to mark elements already included in current permutation

if (path.size() == nums.length)Check if current permutation is complete to add to results

for (int i = 0; i < nums.length; i++)Try each element as next candidate if unused

path.remove(path.size() - 1)Backtrack by removing last element to explore other permutations

used[i] = trueMark element as used before recursion to avoid duplicates

used[i] = falseUnmark element after recursion to allow other permutations

path.add(nums[i])Add current element to the path being built

backtrack(nums, used, path, res)Recursive call to continue building permutations

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

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> path;
        vector<bool> used(nums.size(), false);
        backtrack(nums, used, path, res);
        return res;
    }

private:
    void backtrack(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& res) {
        if (path.size() == nums.size()) {
            res.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (used[i]) continue;
            used[i] = true;
            path.push_back(nums[i]);
            backtrack(nums, used, path, res);
            path.pop_back();
            used[i] = false;
        }
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> result = sol.permute(nums);
    for (auto &perm : result) {
        for (int num : perm) cout << num << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

vector<bool> used(nums.size(), false)Track which elements are included to avoid duplicates in current permutation

if (path.size() == nums.size())Base case: permutation complete, add to results

for (int i = 0; i < nums.size(); i++)Try each unused element as next candidate

path.pop_back()Backtrack by removing last element to try other options

used[i] = trueMark element as used before recursion to avoid duplicates

used[i] = falseUnmark element after recursion to allow other permutations

path.push_back(nums[i])Add current element to the path being built

backtrack(nums, used, path, res)Recursive call to continue building permutations

function permute(nums) {
    const res = [];
    const used = new Array(nums.length).fill(false);
    const path = [];

    function backtrack() {
        if (path.length === nums.length) {
            res.push([...path]);
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            path.push(nums[i]);
            backtrack();
            path.pop();
            used[i] = false;
        }
    }

    backtrack();
    return res;
}

// Test
console.log(permute([1,2,3]));

Line Notes

const used = new Array(nums.length).fill(false)Boolean array to mark elements already used in current permutation

if (path.length === nums.length)Check if permutation is complete to add a copy to results

for (let i = 0; i < nums.length; i++)Try each unused element as next candidate

path.pop()Backtrack by removing last element to explore other permutations

used[i] = trueMark element as used before recursion to avoid duplicates

used[i] = falseUnmark element after recursion to allow other permutations

path.push(nums[i])Add current element to the path being built

backtrack()Recursive call to continue building permutations

⏱

Complexity

TimeO(n! * n)

SpaceO(n) recursion stack + O(n) used array + O(n! * n) output

There are n! permutations, each of length n, and copying each permutation takes O(n). The recursion stack and used array take O(n) space.

💡 For n=3, 3! = 6 permutations, so about 6*3=18 operations; for n=8, 8! = 40320 permutations, which is much larger.

Interview Verdict: Accepted

This approach is correct and accepted for small inputs, but factorial growth limits scalability.

🧠

Backtracking with In-Place Swapping

💡 This approach avoids extra space for used arrays by swapping elements in place, which is more space efficient and often preferred in interviews. It also helps understand how to manipulate the input array directly to generate permutations.

Intuition

Fix one element at a time by swapping it with each candidate element, then recurse on the remaining elements.

Algorithm

1. Start from index 0, swap it with every index from current to end.
2. Recurse by fixing the next index.
3. When index reaches array length, add current permutation to results.
4. Backtrack by swapping back to restore original order.

💡 Swapping in place avoids extra bookkeeping and makes the recursion cleaner but requires careful swap-back to avoid corrupting input.

</>

Code

from typing import List

def permute(nums: List[int]) -> List[List[int]]:
    res = []

    def backtrack(start=0):
        if start == len(nums):
            res.append(nums[:])
            return
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]

    backtrack()
    return res

# Driver code
if __name__ == '__main__':
    print(permute([1,2,3]))

Line Notes

def backtrack(start=0)Start index indicates the position to fix in the permutation

if start == len(nums)Base case: all positions fixed, add a copy of current permutation

for i in range(start, len(nums))Try swapping current index with each candidate index

nums[start], nums[i] = nums[i], nums[start]Swap back to restore original order for next iteration

backtrack(start + 1)Recurse to fix next position

res.append(nums[:])Add a copy of current permutation to results

import java.util.*;

public class Permutations {
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums, 0, res);
        return res;
    }

    private static void backtrack(int[] nums, int start, List<List<Integer>> res) {
        if (start == nums.length) {
            List<Integer> permutation = new ArrayList<>();
            for (int num : nums) permutation.add(num);
            res.add(permutation);
            return;
        }
        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            backtrack(nums, start + 1, res);
            swap(nums, start, i);
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        System.out.println(permute(nums));
    }
}

Line Notes

backtrack(nums, 0, res)Start recursion fixing elements from index 0

if (start == nums.length)Base case: all elements fixed, add current permutation

for (int i = start; i < nums.length; i++)Try swapping current index with each candidate index

swap(nums, start, i)Swap back to restore original order for next iteration

backtrack(nums, start + 1, res)Recurse to fix next position

res.add(permutation)Add a copy of current permutation to results

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

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        backtrack(nums, 0, res);
        return res;
    }

private:
    void backtrack(vector<int>& nums, int start, vector<vector<int>>& res) {
        if (start == nums.size()) {
            res.push_back(nums);
            return;
        }
        for (int i = start; i < nums.size(); i++) {
            swap(nums[start], nums[i]);
            backtrack(nums, start + 1, res);
            swap(nums[start], nums[i]);
        }
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> result = sol.permute(nums);
    for (auto &perm : result) {
        for (int num : perm) cout << num << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

backtrack(nums, 0, res)Begin recursion fixing elements starting at index 0

if (start == nums.size())Base case: all elements fixed, add current permutation

for (int i = start; i < nums.size(); i++)Try swapping current index with each candidate index

swap(nums[start], nums[i])Swap back to restore original order for next iteration

backtrack(nums, start + 1, res)Recurse to fix next position

res.push_back(nums)Add a copy of current permutation to results

function permute(nums) {
    const res = [];

    function backtrack(start = 0) {
        if (start === nums.length) {
            res.push(nums.slice());
            return;
        }
        for (let i = start; i < nums.length; i++) {
            [nums[start], nums[i]] = [nums[i], nums[start]];
            backtrack(start + 1);
            [nums[start], nums[i]] = [nums[i], nums[start]];
        }
    }

    backtrack();
    return res;
}

// Test
console.log(permute([1,2,3]));

Line Notes

function backtrack(start = 0)Start index indicates which position to fix next

if (start === nums.length)Base case: all positions fixed, add a copy of current permutation

for (let i = start; i < nums.length; i++)Try swapping current index with each candidate index

[nums[start], nums[i]] = [nums[i], nums[start]]Swap back to restore original order for next iteration

backtrack(start + 1)Recurse to fix next position

res.push(nums.slice())Add a copy of current permutation to results

⏱

Complexity

TimeO(n! * n)

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

Same factorial time complexity, but no extra used array space. Swapping is done in place.

💡 This approach saves space by modifying the input array directly, which is often preferred in interviews.

Interview Verdict: Accepted

This is the preferred approach in interviews due to its clarity and space efficiency.

🧠

Iterative Approach Using Heap's Algorithm

💡 Heap's algorithm generates permutations by swapping elements iteratively, which can be more efficient and avoids recursion stack overhead. It is a classic algorithm that uses counters to control swaps systematically.

Intuition

Use an array of counters to control swaps and generate permutations by swapping elements based on these counters.

Algorithm

1. Initialize an array c of counters with zeros.
2. Add the initial permutation to results.
3. Iterate i from 0 to n-1, incrementing counters and swapping elements accordingly.
4. When counters[i] < i, swap elements and reset i to 0; else reset counters[i] and increment i.

💡 This algorithm systematically generates permutations by controlling swaps with counters, avoiding recursion.

</>

Code

from typing import List

def permute(nums: List[int]) -> List[List[int]]:
    res = [nums[:]]
    c = [0] * len(nums)
    i = 0
    while i < len(nums):
        if c[i] < i:
            if i % 2 == 0:
                nums[0], nums[i] = nums[i], nums[0]
            else:
                nums[c[i]], nums[i] = nums[i], nums[c[i]]
            res.append(nums[:])
            c[i] += 1
            i = 0
        else:
            c[i] = 0
            i += 1
    return res

# Driver code
if __name__ == '__main__':
    print(permute([1,2,3]))

Line Notes

res = [nums[:]]Start with the initial permutation in results

c = [0] * len(nums)Counters array to control swaps for each position

i = 0Reset index to start over after swap

while i < len(nums)Loop until all permutations generated

if c[i] < iCheck if current counter allows a swap

if i % 2 == 0Swap with first element if i is even

elseReset counter and move to next index if no swap possible

res.append(nums[:])Add a copy of current permutation to results

c[i] += 1Increment counter after swap

c[i] = 0Reset counter to zero

i += 1Move to next index

import java.util.*;

public class Permutations {
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> initial = new ArrayList<>();
        for (int num : nums) initial.add(num);
        res.add(new ArrayList<>(initial));

        int n = nums.length;
        int[] c = new int[n];
        int i = 0;
        while (i < n) {
            if (c[i] < i) {
                if (i % 2 == 0) {
                    swap(nums, 0, i);
                } else {
                    swap(nums, c[i], i);
                }
                List<Integer> perm = new ArrayList<>();
                for (int num : nums) perm.add(num);
                res.add(perm);
                c[i] += 1;
                i = 0;
            } else {
                c[i] = 0;
                i++;
            }
        }
        return res;
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        System.out.println(permute(nums));
    }
}

Line Notes

res.add(new ArrayList<>(initial))Add initial permutation to results

int[] c = new int[n]Counters array to control swaps

int i = 0Initialize index to control iteration over counters

while (i < n)Loop to generate all permutations iteratively

if (c[i] < i)Check if current counter allows a swap

if (i % 2 == 0)Swap with first element if i is even

elseReset counter and move to next index if no swap possible

res.add(perm)Add a copy of current permutation to results

c[i] += 1Increment counter after swap

i = 0Reset index to start over after swap

c[i] = 0Reset counter to zero

i++Move to next index

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

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        res.push_back(nums);
        vector<int> c(nums.size(), 0);
        int i = 0;
        while (i < nums.size()) {
            if (c[i] < i) {
                if (i % 2 == 0) {
                    swap(nums[0], nums[i]);
                } else {
                    swap(nums[c[i]], nums[i]);
                }
                res.push_back(nums);
                c[i] += 1;
                i = 0;
            } else {
                c[i] = 0;
                i++;
            }
        }
        return res;
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> result = sol.permute(nums);
    for (auto &perm : result) {
        for (int num : perm) cout << num << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

res.push_back(nums)Add a copy of current permutation to results

vector<int> c(nums.size(), 0)Counters array to control swaps

int i = 0Initialize index to control iteration over counters

while (i < nums.size())Iterate until all permutations generated

if (c[i] < i)Check if current counter allows a swap

if (i % 2 == 0)Swap with first element if i is even

elseReset counter and move to next index if no swap possible

c[i] += 1Increment counter after swap

i = 0Reset index to start over after swap

c[i] = 0Reset counter to zero

i++Move to next index

function permute(nums) {
    const res = [nums.slice()];
    const c = new Array(nums.length).fill(0);
    let i = 0;
    while (i < nums.length) {
        if (c[i] < i) {
            if (i % 2 === 0) {
                [nums[0], nums[i]] = [nums[i], nums[0]];
            } else {
                [nums[c[i]], nums[i]] = [nums[i], nums[c[i]]];
            }
            res.push(nums.slice());
            c[i] += 1;
            i = 0;
        } else {
            c[i] = 0;
            i++;
        }
    }
    return res;
}

// Test
console.log(permute([1,2,3]));

Line Notes

const res = [nums.slice()]Start results with initial permutation

const c = new Array(nums.length).fill(0)Counters array to control swaps

let i = 0Initialize index to control iteration over counters

while (i < nums.length)Loop to generate all permutations iteratively

if (c[i] < i)Check if current counter allows a swap

if (i % 2 === 0)Swap with first element if i is even

elseReset counter and move to next index if no swap possible

res.push(nums.slice())Add a copy of current permutation to results

c[i] += 1Increment counter after swap

i = 0Reset index to start over after swap

c[i] = 0Reset counter to zero

i++Move to next index

⏱

Complexity

TimeO(n! * n)

SpaceO(n) counters + O(n! * n) output

Heap's algorithm generates all permutations with swaps controlled by counters, avoiding recursion stack overhead.

💡 This iterative approach is useful when recursion depth is a concern or when you want a non-recursive solution.

Interview Verdict: Accepted

This approach is less common but useful to know as an alternative to recursion.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, code the in-place swapping backtracking approach for clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force with Used Array	O(n! * n)	O(n) used array + O(n) recursion stack + O(n! * n) output	Yes (deep recursion)	Yes	Good to mention for clarity, but not preferred to code
2. Backtracking with In-Place Swapping	O(n! * n)	O(n) recursion stack + O(n! * n) output	Yes (deep recursion)	Yes	Preferred approach to code in interviews
3. Iterative Heap's Algorithm	O(n! * n)	O(n) counters + O(n! * n) output	No	Yes	Mention as alternative; rarely coded in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach, and progressively optimize. Practice coding and testing each approach.

How to Present

Clarify input constraints and output format.State the brute force backtracking approach with used array.Explain optimization using in-place swapping.Mention iterative Heap's algorithm if time permits.Code the preferred approach (in-place swapping) carefully.Test with edge cases and explain complexity.

Time Allocation

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

What the Interviewer Tests

Interviewer tests your understanding of backtracking, recursion, and ability to generate all permutations without duplicates or misses. They also check for optimization and code clarity.

Common Follow-ups

• How to handle duplicates in input? → Use sorting and skip duplicates during recursion.
• Can you generate permutations iteratively? → Yes, using Heap's algorithm or lexicographic next permutation.

💡 These follow-ups test your ability to adapt the solution to variations and your knowledge of alternative algorithms.

🔍

Pattern Recognition

When to Use

1) Asked to generate all orderings of distinct elements; 2) Problem involves permutations or rearrangements; 3) Need to explore all possible sequences; 4) Backtracking or recursion is a natural fit.

Signature Phrases

all possible permutationsreturn all orderingsgenerate every arrangement

NOT This Pattern When

Problems asking for combinations or subsets without order, or problems focused on counting permutations without generating them.

Similar Problems

Next Permutation - generate the next lexicographical permutationPermutations II - handle duplicates in inputCombinations - generate subsets instead of orderings

Practice

1. You need to partition a string into substrings such that every substring is a palindrome. Which algorithmic approach guarantees finding all possible palindrome partitions efficiently by pruning invalid partitions early?

easy

A. Backtracking that explores all substring partitions and checks palindrome validity dynamically

B. Dynamic programming that counts the number of palindromic substrings without generating partitions

C. Greedy approach that picks the longest palindrome substring at each step

D. Breadth-first search that generates partitions level by level without palindrome checks

Solution

1. Step 1: Understand problem requirements

   The problem requires generating all palindrome partitions, not just counting or finding one.

2. Step 2: Identify suitable algorithm

   Backtracking explores all partitions and prunes invalid ones by checking palindrome substrings dynamically, ensuring completeness and correctness.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking with palindrome checks finds all partitions [OK]

Hint: Backtracking explores all partitions with palindrome pruning [OK]

Common Mistakes:

• Assuming greedy longest palindrome picks all partitions
• Confusing counting palindromes with generating partitions
• Ignoring palindrome checks in BFS

2. Consider this modified code snippet for generating parentheses. Which line contains a subtle bug that can cause invalid sequences to be generated?

medium

A. Line with 'if close_count <= open_count:' condition

B. Line with 's.pop()' after backtrack calls

C. Line with 'if open_count < n:' condition

D. Line with 'if len(s) == 2 * n:' base case

Solution

1. Step 1: Examine close_count condition

   The condition 'close_count <= open_count' allows adding ')' even when close_count equals open_count, which can produce invalid sequences.

2. Step 2: Correct condition

   The correct condition is 'close_count < open_count' to ensure ')' is added only when there are unmatched '('.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing to '<' fixes invalid sequence generation [OK]

Hint: Close count must be strictly less than open count [OK]

Common Mistakes:

• Using <= instead of < for close_count condition
• Forgetting to pop after recursion

3. What is the time complexity of the bitmask backtracking solution for counting all N-Queens solutions on an nxn board?

medium

A. O(n^n) because each row tries all columns independently

B. O(2^n) due to bitmask operations over all subsets of columns

C. O(n^3) from checking conflicts and iterating over rows and columns

D. O(n!) because each queen placement reduces available columns by one

Solution

1. Step 1: Identify branching factor per row

   Each row places one queen in a column not attacked by previous queens, reducing choices roughly by one each time.

2. Step 2: Calculate total recursive calls

   Thus, total calls approximate n x (n-1) x (n-2) x ... = n! permutations.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Backtracking prunes invalid columns, yielding O(n!) complexity [OK]

Hint: N-Queens backtracking explores permutations -> O(n!) [OK]

Common Mistakes:

• Confusing bitmask ops with exponential subsets
• Assuming polynomial due to pruning

4. What is the time complexity of the bitmask-optimized backtracking solution for the N-Queens problem, and why is the common misconception that it is O(n^3) incorrect?

medium

A. O(n^3) because there are three nested loops over rows, columns, and diagonals

B. O(2^n) because bitmasking iterates over all subsets of columns

C. O(n!) because each row places one queen and pruning reduces the search space factorially

D. O(n^2) because each queen placement checks all previous rows and columns

Solution

1. Step 1: Identify the branching factor per row

   Each row places exactly one queen, and pruning avoids invalid columns and diagonals, reducing choices drastically.

2. Step 2: Understand factorial growth

   Because queens cannot share columns, the number of ways to place queens is at most n!; pruning reduces this further but worst-case remains O(n!).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bitmask pruning reduces search to permutations of columns [OK]

Hint: N-Queens search space is permutations, not polynomial loops [OK]

Common Mistakes:

• Assuming nested loops imply cubic time
• Confusing bitmask subsets with full subsets
• Ignoring pruning effect

5. Suppose the problem is modified so that numbers can be reused multiple times in the arrangement. Which change to the backtracking algorithm correctly adapts to this variant?

hard

A. Keep the 'used' bitmask but reset bits after each recursive call to allow reuse.

B. Remove the 'used' bitmask and allow all numbers at every position, checking divisibility only.

C. Use a frequency array to track counts of each number and decrement/increment during recursion.

D. Modify the divisibility condition to allow partial matches and keep the bitmask unchanged.

Solution

1. Step 1: Understand reuse implication

   Allowing reuse means numbers are no longer unique per position, so tracking used numbers is unnecessary.

2. Step 2: Adapt algorithm

   Removing the 'used' bitmask and checking only divisibility conditions at each position correctly counts valid arrangements with reuse.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Without uniqueness constraint, 'used' tracking is redundant [OK]

Hint: Reuse means no need to track used numbers [OK]

Common Mistakes:

• Trying to reset bitmask bits incorrectly
• Using frequency arrays unnecessarily