Practice
nums after calling next_permutation([1, 3, 2])?Solution
Step 1: Trace the pivot search
Start with i = 1 (index of 3). Since nums[1]=3 >= nums[2]=2, decrement i to 0. nums[0]=1 < nums[1]=3, so pivot i=0.Step 2: Find j to swap with pivot
Start j=2 (value 2). nums[2]=2 > nums[0]=1, so j=2. Swap nums[0] and nums[2]: array becomes [2,3,1]. Then reverse suffix from i+1=1 to end: reverse [3,1] -> [1,3]. Final array: [2,1,3].Final Answer:
Option C -> Option CQuick Check:
Array changes from [1,3,2] to [2,1,3] after next permutation [OK]
- Swapping with wrong element
- Not reversing suffix after swap
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
print(permute([1,2,3]))
What is the value of the variable res after the algorithm completes?Solution
Step 1: Trace initial state and first swaps
Start with [1,2,3], res = [[1,2,3]]. For i=1 (odd), swap nums[c[1]] and nums[1], c[1]=0, swap nums[0] and nums[1] -> [2,1,3], append to res.Step 2: Continue iterations and record permutations
Following Heap's algorithm, the permutations generated in order are: [1,2,3], [2,1,3], [3,1,2], [1,3,2], [3,2,1], [2,3,1].Final Answer:
Option D -> Option DQuick Check:
Matches Heap's algorithm output order for n=3 [OK]
- Confusing swap indices or order of permutations generated
Solution
Step 1: Analyze bit shift operation
Bitmask uses 0-based indexing, so bit for number num should be 1 << (num - 1), not 1 << num.Step 2: Consequence of incorrect bit shift
Incorrect bit shifts cause wrong bits to be set/checked, leading to missing or duplicate counts.Final Answer:
Option A -> Option AQuick Check:
Correct bit shift is critical for accurate used-state tracking [OK]
- Off-by-one bit shifts
- Forgetting to unmark used numbers
Solution
Step 1: Identify branching factor per recursion
From each cell, first character has 4 directions, subsequent steps have at most 3 (excluding the cell we came from).Step 2: Calculate total complexity
For each of N cells, explore up to 3^L paths, so total time is O(N * 3^L).Final Answer:
Option B -> Option BQuick Check:
3^L accounts for pruning revisits, not 4^L [OK]
- Assuming 4^L for all steps
- Confusing L with N in complexity
Solution
Step 1: Understand reuse requirement
Unlimited reuse means elements can be chosen multiple times at each recursion level, so swapping and incrementing start index is not suitable.Step 2: Identify correct approach
Backtracking without swapping, iterating over all elements at each recursion level, and using a 'used' boolean array to skip duplicates at the same depth ensures unique permutations with reuse.Step 3: Evaluate other options
Removing 'seen' causes duplicates; swapping without incrementing start index breaks logic; filtering duplicates after generation is inefficient.Final Answer:
Option A -> Option AQuick Check:
Backtracking with reuse requires iteration over all elements each recursion, not swapping with start index increment [OK]
- Trying to reuse elements by swapping without adjusting recursion index or skipping duplicates properly
