Next Permutation

🎯

Next Permutation

mediumBACKTRACKINGAmazonGoogleFacebook

Imagine you have a list of numbers representing a password combination, and you want to find the next possible combination in lexicographical order to try next.

💡 This problem asks for the next lexicographically greater permutation of a sequence. Beginners often struggle because it requires understanding how permutations are ordered and how to manipulate the sequence in-place to get the next permutation without generating all permutations.

📋

Problem Statement

Given an array of integers nums representing a permutation, modify nums in-place to the next lexicographically greater permutation of numbers. If such arrangement is not possible, rearrange it as the lowest possible order (i.e., sorted in ascending order). The replacement must be in-place with only constant extra memory.

1 ≤ nums.length ≤ 10^5-10^9 ≤ nums[i] ≤ 10^9

💡

Example

Input"[1,2,3]"

Output[1,3,2]

The next permutation after 1,2,3 is 1,3,2.

Input"[3,2,1]"

Output[1,2,3]

3,2,1 is the highest permutation, so we return the lowest permutation 1,2,3.

Input"[1,1,5]"

Output[1,5,1]

Next permutation after 1,1,5 is 1,5,1.

• Single element array [1] → output [1]
• All elements equal [2,2,2] → output [2,2,2]
• Strictly descending order [5,4,3,2,1] → output [1,2,3,4,5]
• Array with duplicates [1,3,2,3] → output [1,3,3,2]

⚠️

Common Mistakes

Not handling the case when the entire array is descending

Code fails to reset to lowest permutation, causing wrong output

✅ Add condition to reverse entire array if no pivot found

Swapping pivot with wrong element (not the smallest greater element)

Next permutation is incorrect or not lexicographically next

✅ Scan from right to find the first element greater than pivot to swap

Not reversing the suffix after swapping

Suffix remains in descending order, so permutation is not minimal next

✅ Reverse the suffix after pivot to get the smallest lex order suffix

Using extra space or generating all permutations

Solution is inefficient and may time out on large inputs

✅ Implement in-place approach with O(1) extra space

Incorrectly handling duplicates

Next permutation may skip valid permutations or produce duplicates

✅ Algorithm naturally handles duplicates by scanning and swapping correctly

🧠

Brute Force (Generate All Permutations and Find Next)

💡 This approach exists to build intuition by brute forcing all permutations and then finding the next one. It is impractical for large inputs but helps understand the problem deeply.

Intuition

Generate all permutations of the array, sort them lexicographically, then find the current permutation and return the next one in order.

Algorithm

1. Generate all permutations of the input array.
2. Sort all permutations lexicographically.
3. Find the index of the current permutation in the sorted list.
4. Return the permutation at the next index, or the first if current is last.

💡 This algorithm is conceptually simple but computationally expensive because generating all permutations grows factorially.

</>

Code

from itertools import permutations

def next_permutation(nums):
    perms = sorted(set(permutations(nums)))
    curr = tuple(nums)
    idx = perms.index(curr)
    next_idx = (idx + 1) % len(perms)
    nums[:] = perms[next_idx]

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

Line Notes

from itertools import permutationsImport permutations to generate all permutations easily

perms = sorted(set(permutations(nums)))Generate all unique permutations and sort them lex order

idx = perms.index(curr)Find the current permutation's index in the sorted list

nums[:] = perms[next_idx]Modify input array in-place to the next permutation

import java.util.*;

public class NextPermutationBrute {
    public static void nextPermutation(int[] nums) {
        List<List<Integer>> perms = new ArrayList<>();
        permute(nums, 0, perms);
        perms.sort((a,b) -> {
            for (int i = 0; i < a.size(); i++) {
                if (!a.get(i).equals(b.get(i))) return a.get(i) - b.get(i);
            }
            return 0;
        });
        List<Integer> curr = new ArrayList<>();
        for (int num : nums) curr.add(num);
        int idx = perms.indexOf(curr);
        List<Integer> next = perms.get((idx + 1) % perms.size());
        for (int i = 0; i < nums.length; i++) nums[i] = next.get(i);
    }

    private static void permute(int[] nums, int start, List<List<Integer>> perms) {
        if (start == nums.length) {
            List<Integer> perm = new ArrayList<>();
            for (int num : nums) perm.add(num);
            if (!perms.contains(perm)) perms.add(perm);
            return;
        }
        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            permute(nums, start + 1, perms);
            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;
    }

    // Driver code
    public static void main(String[] args) {
        int[] arr = {1,2,3};
        nextPermutation(arr);
        System.out.println(Arrays.toString(arr)); // Output: [1,3,2]
    }
}

Line Notes

List<List<Integer>> perms = new ArrayList<>();Store all permutations generated

permute(nums, 0, perms);Generate all permutations recursively

perms.sort((a,b) -> {...});Sort permutations lex order using comparator

int idx = perms.indexOf(curr);Find current permutation index to get next

#include <bits/stdc++.h>
using namespace std;

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

void nextPermutation(vector<int>& nums) {
    vector<vector<int>> perms;
    permute(nums, 0, perms);
    sort(perms.begin(), perms.end());
    auto it = find(perms.begin(), perms.end(), nums);
    int idx = distance(perms.begin(), it);
    nums = perms[(idx + 1) % perms.size()];
}

int main() {
    vector<int> arr = {1,2,3};
    nextPermutation(arr);
    for (int x : arr) cout << x << ' '; // Output: 1 3 2
    cout << '\n';
    return 0;
}

Line Notes

void permute(vector<int>& nums, int start, vector<vector<int>>& perms)Recursive function to generate all permutations

sort(perms.begin(), perms.end());Sort all permutations lexicographically

auto it = find(perms.begin(), perms.end(), nums);Find current permutation's position

nums = perms[(idx + 1) % perms.size()];Assign next permutation or wrap to first

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

function nextPermutation(nums) {
    let perms = [];
    permute(nums, 0, perms);
    perms.sort((a,b) => {
        for (let i = 0; i < a.length; i++) {
            if (a[i] !== b[i]) return a[i] - b[i];
        }
        return 0;
    });
    let currStr = nums.join(',');
    let idx = perms.findIndex(p => p.join(',') === currStr);
    let next = perms[(idx + 1) % perms.length];
    for (let i = 0; i < nums.length; i++) nums[i] = next[i];
}

// Driver code
let arr = [1,2,3];
nextPermutation(arr);
console.log(arr); // Output: [1,3,2]

Line Notes

function permute(nums, start, perms)Recursive helper to generate permutations

perms.sort((a,b) => {...});Sort permutations lex order for indexing

let idx = perms.findIndex(p => p.join(',') === currStr);Find current permutation index

for (let i = 0; i < nums.length; i++) nums[i] = next[i];Overwrite input array in-place

⏱

Complexity

TimeO(n! * n log n) due to generating all permutations and sorting

SpaceO(n! * n) to store all permutations

Generating all permutations is factorial in n, sorting them adds n log n factor, and storing them requires large memory.

💡 For n=10, this means over 3 million permutations, which is impractical to compute or store.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem and verify correctness on small inputs.

🧠

Better Approach (Find Pivot and Swap)

💡 This approach improves efficiency by directly finding the next permutation using a known pattern, avoiding generating all permutations.

Intuition

Traverse from the end to find the first decreasing element (pivot), then find the smallest element larger than pivot to the right, swap them, and reverse the suffix after pivot.

Algorithm

1. Scan from right to left to find the first index 'i' where nums[i] < nums[i+1].
2. If no such index exists, reverse the entire array and return.
3. Otherwise, scan from right to find the first index 'j' where nums[j] > nums[i].
4. Swap nums[i] and nums[j].
5. Reverse the subarray nums[i+1:] to get the next permutation.

💡 This algorithm cleverly uses the properties of permutations to find the next lexicographical order without generating all permutations.

</>

Code

def next_permutation(nums):
    i = len(nums) - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        j = len(nums) - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    left, right = i + 1, len(nums) - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

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

Line Notes

i = len(nums) - 2Start from second last element to find pivot

while i >= 0 and nums[i] >= nums[i + 1]Find first decreasing element from right

if i >= 0:If pivot found, find element to swap with

while nums[j] <= nums[i]Find rightmost element greater than pivot

import java.util.*;

public class NextPermutationBetter {
    public static void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;
        if (i >= 0) {
            int j = nums.length - 1;
            while (nums[j] <= nums[i]) j--;
            swap(nums, i, j);
        }
        reverse(nums, i + 1, nums.length - 1);
    }

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

    private static void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start++, end--);
        }
    }

    // Driver code
    public static void main(String[] args) {
        int[] arr = {1,2,3};
        nextPermutation(arr);
        System.out.println(Arrays.toString(arr)); // Output: [1,3,2]
    }
}

Line Notes

int i = nums.length - 2;Start from second last index to find pivot

while (i >= 0 && nums[i] >= nums[i + 1]) i--;Find first decreasing element from right

if (i >= 0)If pivot found, find element to swap with

reverse(nums, i + 1, nums.length - 1);Reverse suffix to get next permutation

#include <bits/stdc++.h>
using namespace std;

void nextPermutation(vector<int>& nums) {
    int i = (int)nums.size() - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;
    if (i >= 0) {
        int j = (int)nums.size() - 1;
        while (nums[j] <= nums[i]) j--;
        swap(nums[i], nums[j]);
    }
    reverse(nums.begin() + i + 1, nums.end());
}

int main() {
    vector<int> arr = {1,2,3};
    nextPermutation(arr);
    for (int x : arr) cout << x << ' '; // Output: 1 3 2
    cout << '\n';
    return 0;
}

Line Notes

int i = (int)nums.size() - 2;Start from second last element to find pivot

while (i >= 0 && nums[i] >= nums[i + 1]) i--;Find first decreasing element from right

if (i >= 0)If pivot found, find element to swap with

reverse(nums.begin() + i + 1, nums.end());Reverse suffix to get next permutation

function nextPermutation(nums) {
    let i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;
    if (i >= 0) {
        let j = nums.length - 1;
        while (nums[j] <= nums[i]) j--;
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    let left = i + 1, right = nums.length - 1;
    while (left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]];
        left++;
        right--;
    }
}

// Driver code
let arr = [1,2,3];
nextPermutation(arr);
console.log(arr); // Output: [1,3,2]

Line Notes

let i = nums.length - 2;Start from second last index to find pivot

while (i >= 0 && nums[i] >= nums[i + 1]) i--;Find first decreasing element from right

if (i >= 0)If pivot found, find element to swap with

while (left < right)Reverse suffix to get next permutation

⏱

Complexity

TimeO(n)

SpaceO(1)

We scan the array from the end a few times and reverse a suffix in-place, all linear operations.

💡 For n=10^5, this means about 3 passes over the array, which is efficient and feasible.

Interview Verdict: Accepted

This is the optimal approach expected in interviews for this problem.

🧠

Space Optimized (In-place with Two Pointers and Reverse)

💡 This approach is the same as the better approach but emphasizes in-place operations and minimal extra space, which is critical for large inputs.

Intuition

By scanning from the right and swapping only necessary elements, then reversing the suffix in-place, we avoid extra memory and achieve optimal performance.

Algorithm

1. Find the pivot index from right where nums[i] < nums[i+1].
2. If pivot not found, reverse entire array and return.
3. Find the rightmost successor to pivot greater than nums[i].
4. Swap pivot and successor.
5. Reverse the suffix starting at pivot+1.

💡 The key is to reverse only the suffix after swapping to get the next permutation in-place.

</>

Code

def next_permutation(nums):
    i = len(nums) - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        j = len(nums) - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    left, right = i + 1, len(nums) - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

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

Line Notes

i = len(nums) - 2Start from second last element to find pivot

while i >= 0 and nums[i] >= nums[i + 1]Find first decreasing element from right

if i >= 0:If pivot found, find element to swap with

while left < rightReverse suffix in-place to get next permutation

import java.util.*;

public class NextPermutationSpaceOpt {
    public static void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;
        if (i >= 0) {
            int j = nums.length - 1;
            while (nums[j] <= nums[i]) j--;
            swap(nums, i, j);
        }
        reverse(nums, i + 1, nums.length - 1);
    }

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

    private static void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start++, end--);
        }
    }

    // Driver code
    public static void main(String[] args) {
        int[] arr = {1,2,3};
        nextPermutation(arr);
        System.out.println(Arrays.toString(arr)); // Output: [1,3,2]
    }
}

Line Notes

int i = nums.length - 2;Start from second last index to find pivot

while (i >= 0 && nums[i] >= nums[i + 1]) i--;Find first decreasing element from right

if (i >= 0)If pivot found, find element to swap with

reverse(nums, i + 1, nums.length - 1);Reverse suffix in-place to get next permutation

#include <bits/stdc++.h>
using namespace std;

void nextPermutation(vector<int>& nums) {
    int i = (int)nums.size() - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;
    if (i >= 0) {
        int j = (int)nums.size() - 1;
        while (nums[j] <= nums[i]) j--;
        swap(nums[i], nums[j]);
    }
    reverse(nums.begin() + i + 1, nums.end());
}

int main() {
    vector<int> arr = {1,2,3};
    nextPermutation(arr);
    for (int x : arr) cout << x << ' '; // Output: 1 3 2
    cout << '\n';
    return 0;
}

Line Notes

int i = (int)nums.size() - 2;Start from second last element to find pivot

while (i >= 0 && nums[i] >= nums[i + 1]) i--;Find first decreasing element from right

if (i >= 0)If pivot found, find element to swap with

reverse(nums.begin() + i + 1, nums.end());Reverse suffix in-place to get next permutation

function nextPermutation(nums) {
    let i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;
    if (i >= 0) {
        let j = nums.length - 1;
        while (nums[j] <= nums[i]) j--;
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    let left = i + 1, right = nums.length - 1;
    while (left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]];
        left++;
        right--;
    }
}

// Driver code
let arr = [1,2,3];
nextPermutation(arr);
console.log(arr); // Output: [1,3,2]

Line Notes

let i = nums.length - 2;Start from second last index to find pivot

while (i >= 0 && nums[i] >= nums[i + 1]) i--;Find first decreasing element from right

if (i >= 0)If pivot found, find element to swap with

while (left < right)Reverse suffix in-place to get next permutation

⏱

Complexity

TimeO(n)

SpaceO(1)

All operations are done in-place with linear scans and swaps.

💡 This approach is the most efficient and uses minimal memory, ideal for large inputs.

Interview Verdict: Accepted

This is the best practical approach to implement in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 The optimal in-place approach (Approach 2 or 3) is what you should code in 95% of interviews. Brute force is only for conceptual understanding.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n! * n log n)	O(n! * n)	Yes (deep recursion)	Yes	Mention only - never code
2. Better Approach (Pivot and Swap)	O(n)	O(1)	No	N/A	Code this approach
3. Space Optimized (In-place Reverse)	O(n)	O(1)	No	N/A	Code this approach (same as 2)

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the optimal approach, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to show understanding.Step 3: Explain the better approach using pivot and suffix reversal.Step 4: Code the optimal in-place solution carefully.Step 5: Test with edge cases and explain time/space complexity.

Time Allocation

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

What the Interviewer Tests

Interviewer tests your understanding of permutation ordering, ability to optimize from brute force to linear time, and skill in in-place array manipulation.

Common Follow-ups

• How to find previous permutation? → Reverse the logic to find first increasing element from right.
• Can you do this for strings? → Yes, same logic applies to character arrays.

💡 These follow-ups test your ability to adapt the core logic to variations and different data types.

🔍

Pattern Recognition

When to Use

1) Asked for next or previous lexicographical permutation; 2) Input is a sequence or array; 3) Need in-place or efficient solution; 4) Problem involves rearranging elements to next order.

Signature Phrases

next lexicographically greater permutationrearrange to next orderin-place modification

NOT This Pattern When

Generating all permutations without order constraints or problems requiring all permutations explicitly

Similar Problems

Permutation Sequence - find kth permutation using factorial number systemPrevious Permutation - find previous lexicographical permutationNext Greater Element III - next permutation of digits in a number

Practice

1. You need to find the k-th lexicographically smallest permutation of numbers from 1 to n. Which approach guarantees an optimal solution without generating all permutations explicitly?

easy

A. Use a greedy algorithm that swaps elements to reach the k-th permutation directly.

B. Compute factorial values to determine each digit's position and build the permutation directly.

C. Use dynamic programming to count permutations and reconstruct the k-th sequence.

D. Generate all permutations using backtracking and return the k-th one.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the k-th permutation without enumerating all permutations, which is infeasible for large n.

2. Step 2: Identify the approach that uses factorial number system

   Using precomputed factorials, we can determine the index of each digit in the permutation directly, avoiding full enumeration.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Factorial-based direct computation is optimal and avoids timeouts [OK]

Hint: Factorials let you jump directly to the k-th permutation [OK]

Common Mistakes:

• Thinking greedy swaps can find k-th permutation efficiently
• Assuming DP is needed here
• Trying to generate all permutations for large n

2. What is the time complexity of the optimal backtracking solution for the Expression Add Operators problem, where n is the length of the input string? Assume the solution tries all operator insertions and substring splits with pruning and efficient string building.

medium

A. O(4^n) because at each position there are up to 4 choices (3 operators + no operator split)

B. O(n * 3^n) because each digit can be combined with 3 operators and substring splits

C. O(2^n) since only two operators are considered at each step

D. O(n^3) due to substring parsing and operator insertions

Solution

1. Step 1: Identify branching factor per digit

   At each digit, we can insert one of 3 operators (+, -, *) or choose to extend the current operand (no operator), but the main branching factor is 3 operators per split, and substring splits add a factor of n.

2. Step 2: Calculate total complexity

   The total complexity is roughly O(n * 3^n) because for each of the n positions, there are up to 3 operator choices, and substring splits add an n factor.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Exponential branching with 3 operators and substring splits [OK]

Hint: 3 operators per digit and substring splits lead to O(n * 3^n) complexity [OK]

Common Mistakes:

• Confusing substring parsing cost as cubic
• Assuming only 2 operators reduce complexity
• Miscounting branching factor as 4

3. Consider the following code snippet intended to generate unique permutations of an array with duplicates. Which line contains a subtle bug that causes duplicate permutations to be generated?

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

medium

A. Line with 'if i > start and nums[i] == nums[i-1]: continue' (duplicate skipping condition)

B. Line with 'nums.sort()' (sorting input before recursion)

C. Line with 'nums[start], nums[i] = nums[i], nums[start]' before recursion (swap)

D. Line with 'for i in range(start, len(nums)):' (iteration over indices)

Solution

1. Step 1: Analyze duplicate skipping condition

   The condition 'if i > start and nums[i] == nums[i-1]: continue' attempts to skip duplicates but does not consider whether the previous duplicate was used, causing some duplicates to be missed.

2. Step 2: Verify other lines

   Sorting input is correct; swapping before and after recursion is correct; iteration over indices is standard. The bug is in the duplicate skipping logic.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incorrect duplicate skipping causes duplicate permutations [OK]

Hint: Skipping duplicates requires tracking usage, not just comparing adjacent elements [OK]

Common Mistakes:

• Skipping duplicates by only comparing adjacent elements without usage tracking

4. Examine the following code snippet for the Word Search problem. It is almost correct but contains one subtle bug. Identify the line causing the bug.

medium

A. Line where board[r][c] = temp is restored after recursion

B. Line where temp = board[r][c]

C. Line where directions are defined

D. Line missing board[r][c] = '#' to mark visited

Solution

1. Step 1: Identify missing visited marking

   The code does not mark the current cell as visited before recursive calls, allowing revisits.

2. Step 2: Understand impact of missing marking

   Without marking, dfs can revisit the same cell multiple times, causing incorrect matches or infinite loops.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Marking visited cells is essential to prevent reuse [OK]

Hint: Check if visited cells are marked before recursion [OK]

Common Mistakes:

• Forgetting to mark visited cells
• Restoring cell too early

5. Suppose the problem is modified so that digits can be repeated any number of times (reuse allowed), and you want to generate all letter combinations of length n from the given digits. Which modification to the algorithm correctly handles this reuse scenario?

hard

A. Modify backtracking to allow choosing the same digit multiple times by not incrementing the index after each choice until length n is reached

B. Sort digits and generate combinations by picking letters only once per digit

C. Use dynamic programming to store combinations of length k and build up to length n without reuse

D. Use the same iterative queue approach but do not advance the digit index; instead, for each combination, append letters from all digits repeatedly until length n is reached

Solution

1. Step 1: Understand reuse requirement

   Allowing reuse means digits can be chosen multiple times to build combinations of length n.

2. Step 2: Identify correct approach

   Backtracking can be modified to not increment the digit index after choosing a letter, allowing reuse until length n is reached.

3. Step 3: Why other options fail

   Iterative queue approach as-is assumes fixed digit positions; DP without reuse does not handle repeated digits; sorting and picking once per digit ignores reuse.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Backtracking with flexible index handles reuse elegantly [OK]

Hint: Backtracking index controls reuse by not advancing [OK]

Common Mistakes:

• Trying to reuse digits in iterative approach without index control
• Ignoring reuse in DP or sorting