Subsets II (With Duplicates)

🎯

Subsets II (With Duplicates)

mediumBACKTRACKINGAmazonFacebookGoogle

Imagine you have a collection of colored beads, some colors repeating, and you want to find all unique ways to select any number of beads without caring about order.

💡 This problem is about generating all unique subsets from a list that may contain duplicates. Beginners often struggle because duplicates cause repeated subsets, and handling them requires careful logic to avoid redundant results.

📋

Problem Statement

Given an integer array nums that may contain duplicates, return all possible subsets (the power set) without duplicate subsets. The solution set must not contain duplicate subsets. Return the solution in any order.

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

💡

Example

Input"[1,2,2]"

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

Starting from an empty subset, we include or exclude each element. Sorting helps group duplicates so we skip repeated subsets at the same recursion depth.

• Empty input array → output [[]]
• All elements are duplicates, e.g. [2,2,2] → output [[],[2],[2,2],[2,2,2]]
• Array with no duplicates, e.g. [1,2,3] → output all 8 subsets
• Large input with many duplicates → ensure no timeout and no duplicates in output

⚠️

Common Mistakes

Not sorting input before recursion

Duplicates are not adjacent, so skipping duplicates fails, causing repeated subsets.

✅ Always sort input before backtracking to group duplicates.

Skipping duplicates incorrectly (e.g., skipping all duplicates, not just at same recursion level)

Some valid subsets are missed or duplicates remain.

✅ Only skip duplicates when the current index is greater than the start index in the loop.

Modifying the path list without backtracking (not popping after recursion)

Path accumulates extra elements, causing wrong subsets.

✅ Always pop the last element after recursive call to restore state.

Using a set of lists without converting to tuples (in Python)

Runtime error because lists are unhashable.

✅ Convert lists to tuples before adding to set.

🧠

Brute Force (Pure Recursion with Deduplication by Set)

💡 This approach introduces the basic idea of generating all subsets by recursion but uses a set to remove duplicates after generation. It is simple but inefficient and helps understand the problem's nature.

Intuition

Generate all subsets by including or excluding each element recursively. Because duplicates exist, store subsets in a set to avoid duplicates.

Algorithm

1. Sort the input array to group duplicates together.
2. Use recursion to explore two choices at each index: include or exclude the current element.
3. At each recursion leaf, add the current subset to a set to avoid duplicates.
4. Convert the set to a list and return all unique subsets.

💡 The main challenge is duplicates causing repeated subsets; sorting and using a set after generation is a straightforward but costly way to handle this.

</>

Code

from typing import List

def subsetsWithDup(nums: List[int]) -> List[List[int]]:
    nums.sort()
    res = set()
    def backtrack(i, path):
        if i == len(nums):
            res.add(tuple(path))
            return
        # Exclude nums[i]
        backtrack(i + 1, path)
        # Include nums[i]
        backtrack(i + 1, path + [nums[i]])
    backtrack(0, [])
    return [list(t) for t in res]

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

Line Notes

nums.sort()Sort to group duplicates, making it easier to handle them later.

res = set()Use a set to automatically remove duplicate subsets.

if i == len(nums):Base case: when index reaches end, add current subset to results.

res.add(tuple(path))Convert list to tuple to store in set because lists are unhashable.

import java.util.*;

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> res = new HashSet<>();
        backtrack(nums, 0, new ArrayList<>(), res);
        return new ArrayList<>(res);
    }
    private void backtrack(int[] nums, int index, List<Integer> path, Set<List<Integer>> res) {
        if (index == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        // Exclude nums[index]
        backtrack(nums, index + 1, path, res);
        // Include nums[index]
        path.add(nums[index]);
        backtrack(nums, index + 1, path, res);
        path.remove(path.size() - 1);
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.subsetsWithDup(new int[]{1,2,2}));
    }
}

Line Notes

Arrays.sort(nums);Sort input to group duplicates for easier handling.

Set<List<Integer>> res = new HashSet<>();Use a set to avoid duplicate subsets.

if (index == nums.length)Base case: add current subset to results when end reached.

res.add(new ArrayList<>(path));Add a copy of current subset to results to avoid mutation.

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        set<vector<int>> res;
        vector<int> path;
        backtrack(nums, 0, path, res);
        return vector<vector<int>>(res.begin(), res.end());
    }
private:
    void backtrack(vector<int>& nums, int index, vector<int>& path, set<vector<int>>& res) {
        if (index == nums.size()) {
            res.insert(path);
            return;
        }
        // Exclude nums[index]
        backtrack(nums, index + 1, path, res);
        // Include nums[index]
        path.push_back(nums[index]);
        backtrack(nums, index + 1, path, res);
        path.pop_back();
    }
};

// Driver code
int main() {
    Solution sol;
    vector<int> nums = {1,2,2};
    vector<vector<int>> result = sol.subsetsWithDup(nums);
    for (auto &subset : result) {
        cout << "[";
        for (int i = 0; i < subset.size(); ++i) {
            cout << subset[i];
            if (i < subset.size() - 1) cout << ",";
        }
        cout << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort input to group duplicates for easier handling.

set<vector<int>> res;Use a set to automatically remove duplicate subsets.

if (index == nums.size()) {Base case: add current subset to results when end reached.

res.insert(path);Insert current subset into set to avoid duplicates.

function subsetsWithDup(nums) {
    nums.sort((a,b) => a - b);
    const res = new Set();
    function backtrack(i, path) {
        if (i === nums.length) {
            res.add(path.join(','));
            return;
        }
        // Exclude nums[i]
        backtrack(i + 1, path);
        // Include nums[i]
        backtrack(i + 1, path.concat(nums[i]));
    }
    backtrack(0, []);
    return Array.from(res).map(s => s === '' ? [] : s.split(',').map(Number));
}

// Driver code
console.log(subsetsWithDup([1,2,2]));

Line Notes

nums.sort((a,b) => a - b);Sort input to group duplicates for easier handling.

const res = new Set();Use a set to remove duplicate subsets by storing string keys.

if (i === nums.length) {Base case: add current subset to results when end reached.

res.add(path.join(','));Convert subset to string to store in set since arrays are unhashable.

⏱

Complexity

TimeO(2^n * n) due to generating all subsets and converting to tuples/lists

SpaceO(2^n * n) for storing all subsets in the set

We explore all subsets (2^n). Each subset can be up to length n, and storing in a set requires hashing/conversion.

💡 For n=20, this means over a million subsets, which is very slow and memory-heavy.

Interview Verdict: Accepted but inefficient; not suitable for large inputs

This approach works but is too slow for large inputs. It is useful to understand the problem and correctness before optimizing.

🧠

Backtracking with Sorting and Skip Duplicates at Same Recursion Level

💡 This approach improves efficiency by sorting and skipping duplicates during recursion, avoiding generating duplicate subsets in the first place.

Intuition

Sort the array so duplicates are adjacent. When choosing elements at the same recursion depth, skip duplicates to prevent repeated subsets.

Algorithm

1. Sort the input array to group duplicates.
2. Use backtracking to explore subsets starting from an index.
3. At each recursion level, iterate over candidates starting from current index.
4. Skip elements that are the same as the previous one at the same recursion level to avoid duplicates.
5. Add the current path to results at each recursion call.

💡 Skipping duplicates at the same recursion level is the key insight to avoid repeated subsets without extra memory.

</>

Code

from typing import List

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

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

Line Notes

nums.sort()Sort to group duplicates for easy skipping.

res.append(path[:])Add current subset copy to results at each recursion call.

if i > start and nums[i] == nums[i-1]:Skip duplicates at the same recursion level to avoid repeated subsets.

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

import java.util.*;

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), res);
        return res;
    }
    private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
        res.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) continue;
            path.add(nums[i]);
            backtrack(nums, i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.subsetsWithDup(new int[]{1,2,2}));
    }
}

Line Notes

Arrays.sort(nums);Sort input to group duplicates for easy skipping.

res.add(new ArrayList<>(path));Add a copy of current subset to results at each recursion call.

if (i > start && nums[i] == nums[i - 1]) continue;Skip duplicates at the same recursion level to avoid repeated subsets.

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

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        vector<int> path;
        backtrack(nums, 0, path, res);
        return res;
    }
private:
    void backtrack(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& res) {
        res.push_back(path);
        for (int i = start; i < nums.size(); ++i) {
            if (i > start && nums[i] == nums[i - 1]) continue;
            path.push_back(nums[i]);
            backtrack(nums, i + 1, path, res);
            path.pop_back();
        }
    }
};

// Driver code
int main() {
    Solution sol;
    vector<int> nums = {1,2,2};
    vector<vector<int>> result = sol.subsetsWithDup(nums);
    for (auto &subset : result) {
        cout << "[";
        for (int i = 0; i < subset.size(); ++i) {
            cout << subset[i];
            if (i < subset.size() - 1) cout << ",";
        }
        cout << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort input to group duplicates for easy skipping.

res.push_back(path);Add current subset to results at each recursion call.

if (i > start && nums[i] == nums[i - 1]) continue;Skip duplicates at the same recursion level to avoid repeated subsets.

path.pop_back();Backtrack by removing last element to explore other subsets.

function subsetsWithDup(nums) {
    nums.sort((a,b) => a - b);
    const res = [];
    function backtrack(start, path) {
        res.push([...path]);
        for (let i = start; i < nums.length; i++) {
            if (i > start && nums[i] === nums[i - 1]) continue;
            path.push(nums[i]);
            backtrack(i + 1, path);
            path.pop();
        }
    }
    backtrack(0, []);
    return res;
}

// Driver code
console.log(subsetsWithDup([1,2,2]));

Line Notes

nums.sort((a,b) => a - b);Sort input to group duplicates for easy skipping.

res.push([...path]);Add a copy of current subset to results at each recursion call.

if (i > start && nums[i] === nums[i - 1]) continue;Skip duplicates at the same recursion level to avoid repeated subsets.

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

⏱

Complexity

TimeO(2^n * n) due to generating all subsets and copying them

SpaceO(2^n * n) for storing all subsets

We generate all subsets but skip duplicates early, reducing redundant work. Each subset copy costs O(n).

💡 For n=20, this is still large but much faster than brute force with set deduplication.

Interview Verdict: Accepted and efficient for typical interview constraints

This is the standard approach to solve this problem efficiently and is expected in interviews.

🧠

Iterative Approach with Sorting and Skipping Duplicates

💡 This approach uses iteration instead of recursion to build subsets step-by-step, carefully skipping duplicates to avoid repeated subsets.

Intuition

Start with an empty subset. For each number, add it to existing subsets to form new subsets. When duplicates appear, only add to subsets created in the previous step to avoid duplicates.

Algorithm

1. Sort the input array to group duplicates.
2. Initialize result with an empty subset.
3. Iterate over each number in nums.
4. If current number is a duplicate, only extend subsets created in the previous iteration.
5. Otherwise, extend all existing subsets with the current number.
6. Return the result containing all unique subsets.

💡 Tracking the start index for new subsets when duplicates appear is the key to avoid duplicates without recursion.

</>

Code

from typing import List

def subsetsWithDup(nums: List[int]) -> List[List[int]]:
    nums.sort()
    res = [[]]
    start = 0
    for i in range(len(nums)):
        if i > 0 and nums[i] == nums[i - 1]:
            s = start
        else:
            s = 0
        start = len(res)
        for j in range(s, len(res)):
            res.append(res[j] + [nums[i]])
    return res

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

Line Notes

nums.sort()Sort to group duplicates for easy handling.

res = [[]]Start with empty subset in results.

if i > 0 and nums[i] == nums[i - 1]:Detect duplicates to limit extension to new subsets only.

res.append(res[j] + [nums[i]])Create new subsets by adding current number to existing subsets.

import java.util.*;

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        int start = 0;
        for (int i = 0; i < nums.length; i++) {
            int s = 0;
            if (i > 0 && nums[i] == nums[i - 1]) {
                s = start;
            }
            start = res.size();
            int size = res.size();
            for (int j = s; j < size; j++) {
                List<Integer> subset = new ArrayList<>(res.get(j));
                subset.add(nums[i]);
                res.add(subset);
            }
        }
        return res;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.subsetsWithDup(new int[]{1,2,2}));
    }
}

Line Notes

Arrays.sort(nums);Sort to group duplicates for easy handling.

res.add(new ArrayList<>());Initialize results with empty subset.

if (i > 0 && nums[i] == nums[i - 1]) {Detect duplicates to limit extension to new subsets only.

res.add(subset);Add new subset formed by adding current number.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res = {{} };
        int start = 0;
        for (int i = 0; i < nums.size(); ++i) {
            int s = 0;
            if (i > 0 && nums[i] == nums[i - 1]) {
                s = start;
            }
            start = res.size();
            int size = res.size();
            for (int j = s; j < size; ++j) {
                vector<int> subset = res[j];
                subset.push_back(nums[i]);
                res.push_back(subset);
            }
        }
        return res;
    }
};

// Driver code
int main() {
    Solution sol;
    vector<int> nums = {1,2,2};
    vector<vector<int>> result = sol.subsetsWithDup(nums);
    for (auto &subset : result) {
        cout << "[";
        for (int i = 0; i < subset.size(); ++i) {
            cout << subset[i];
            if (i < subset.size() - 1) cout << ",";
        }
        cout << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort to group duplicates for easy handling.

vector<vector<int>> res = {{}};Initialize results with empty subset.

if (i > 0 && nums[i] == nums[i - 1]) {Detect duplicates to limit extension to new subsets only.

res.push_back(subset);Add new subset formed by adding current number.

function subsetsWithDup(nums) {
    nums.sort((a,b) => a - b);
    const res = [[]];
    let start = 0;
    for (let i = 0; i < nums.length; i++) {
        let s = 0;
        if (i > 0 && nums[i] === nums[i - 1]) {
            s = start;
        }
        start = res.length;
        const size = res.length;
        for (let j = s; j < size; j++) {
            res.push(res[j].concat(nums[i]));
        }
    }
    return res;
}

// Driver code
console.log(subsetsWithDup([1,2,2]));

Line Notes

nums.sort((a,b) => a - b);Sort to group duplicates for easy handling.

const res = [[]];Initialize results with empty subset.

if (i > 0 && nums[i] === nums[i - 1]) {Detect duplicates to limit extension to new subsets only.

res.push(res[j].concat(nums[i]));Add new subset formed by adding current number.

⏱

Complexity

TimeO(2^n * n) due to generating all subsets and copying them

SpaceO(2^n * n) for storing all subsets

We build subsets iteratively, skipping duplicates by limiting extension to new subsets only, reducing redundant work.

💡 For n=20, this approach is efficient and avoids recursion stack overhead.

Interview Verdict: Accepted and efficient; good alternative to recursion

This iterative approach is a neat alternative to recursion and is often appreciated in interviews for its clarity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 Approach 2 (backtracking with skip duplicates) is the best to code in interviews for clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Recursion + Set Deduplication)	O(2^n * n)	O(2^n * n)	Yes (deep recursion)	Yes	Mention only - never code due to inefficiency
2. Backtracking with Sorting and Skip Duplicates	O(2^n * n)	O(2^n * n)	Yes (deep recursion)	Yes	Code this approach in 95% of interviews
3. Iterative with Sorting and Skip Duplicates	O(2^n * n)	O(2^n * n)	No	Yes	Good alternative if recursion is not preferred

💼

Interview Strategy

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

How to Present

Step 1: Clarify the problem and ask about duplicates and output format.Step 2: Present the brute force recursive approach with set deduplication to show understanding.Step 3: Improve to backtracking with sorting and skipping duplicates at the same recursion level.Step 4: Optionally present the iterative approach as an alternative.Step 5: Write clean code and test with examples and edge cases.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your understanding of backtracking, handling duplicates, optimization, and clean coding.

Common Follow-ups

• What if input is very large? → Use iterative or pruning to optimize memory.
• Can you generate subsets of fixed size k? → Modify recursion to track subset size.

💡 Follow-ups test your ability to adapt the solution to constraints and variations.

🔍

Pattern Recognition

When to Use

1) Asked to generate all subsets or combinations 2) Input may contain duplicates 3) Need unique subsets 4) Order of subsets does not matter

Signature Phrases

return all possible subsetsthe solution set must not contain duplicate subsets

NOT This Pattern When

Problems asking for permutations without duplicates or subsets with fixed size k only

Similar Problems

Subsets I (No Duplicates) - simpler version without duplicatesCombination Sum II - similar duplicate handling in combinationsPermutations II - duplicate handling in permutations

Practice

1. You need to generate all unique groups of size k from numbers 1 to n without repetition, where order within each group does not matter. Which algorithmic approach guarantees generating all such groups efficiently without duplicates?

easy

A. Backtracking that explores all number choices with pruning to avoid duplicates

B. Greedy selection picking the smallest available number until group size is reached

C. Dynamic programming to count subsets but not generate them explicitly

D. Sorting all numbers and then selecting consecutive sequences of length k

Solution

1. Step 1: Understand the problem requires all unique combinations of size k from n numbers

   Greedy or sorting consecutive sequences do not guarantee all unique combinations without duplicates.

2. Step 2: Backtracking with pruning systematically explores all valid combinations and avoids duplicates by controlling start indices

   This approach ensures all unique groups are generated efficiently.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking with pruning is the standard approach for combinations [OK]

Hint: Backtracking with pruning avoids duplicates efficiently [OK]

Common Mistakes:

• Thinking greedy or sorting consecutive sequences generate all combinations

2. You are given an array of integers and need to find the number of subsets whose bitwise OR equals the maximum possible OR value among all subsets. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach selecting elements with highest bits set first

B. Iterative bitmask enumeration generating all subsets and computing their OR

C. Dynamic programming based on subset sums

D. Sorting the array and using two pointers to find max OR subsets

Solution

1. Step 1: Understand the problem requires checking all subsets

   Since the maximum bitwise OR depends on any combination of elements, all subsets must be considered.

2. Step 2: Identify approach that enumerates all subsets efficiently

   Iterative bitmask enumeration systematically generates all subsets and computes their OR, ensuring no subset is missed.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bitmask enumeration covers all subsets -> optimal [OK]

Hint: Bitmask enumeration covers all subsets exhaustively [OK]

Common Mistakes:

• Assuming greedy selection suffices for max OR
• Confusing subset sum DP with bitwise OR problem

3. Consider the following Python code that generates all subsets of nums = [1, 2, 3]. What is the value of subset when mask = 5 during the iteration?

easy

A. [1, 3]

B. [2, 3]

C. [1, 2]

D. [3]

Solution

1. Step 1: Convert mask=5 to binary

   5 in binary is 101, meaning bits 0 and 2 are set.

2. Step 2: Map bits to indices in nums

   Bit 0 corresponds to nums[0]=1, bit 2 corresponds to nums[2]=3, so subset = [1, 3].

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mask 5 selects elements at positions 0 and 2 -> [1, 3] [OK]

Hint: Mask bits correspond to included elements [OK]

Common Mistakes:

• Off-by-one bit indexing
• Confusing mask bits with element values

4. What is the time complexity of the bitmask enumeration approach for counting the number of max bitwise-OR subsets in an array of length n?

medium

A. O(n^2)

B. O(n!)

C. O(2^n)

D. O(n * 2^n)

Solution

1. Step 1: Identify outer loop over all subsets

   There are 2^n subsets, so outer loop runs 2^n times.

2. Step 2: Identify inner loop over elements for each subset

   For each subset, we check up to n elements to compute OR, so inner loop is O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   2^n subsets x n elements per subset -> O(n * 2^n) [OK]

Hint: Each subset requires checking n elements -> O(n * 2^n) [OK]

Common Mistakes:

• Confusing 2^n subsets with O(2^n) ignoring inner loop
• Assuming quadratic or factorial complexity

5. Suppose the problem is modified so that letters can be toggled multiple times, allowing reuse of characters in permutations (e.g., toggling the same letter case multiple times in different positions). Which modification to the backtracking approach correctly handles this variant without generating duplicates?

hard

A. Use a visited set to track permutations and skip duplicates after generation

B. Modify recursion to allow toggling letters multiple times but prune branches that revisit the same index

C. Change the algorithm to generate permutations with replacement by increasing recursion depth beyond string length

D. Use iterative BFS with a queue that enqueues toggled strings and avoids revisiting states

Solution

1. Step 1: Understand reuse variant

   Allowing reuse means letters can be toggled multiple times in different positions, increasing state space and possible duplicates.

2. Step 2: Identify correct approach

   Iterative BFS with a queue can track states and avoid revisiting duplicates efficiently, unlike naive recursion which may generate duplicates or infinite loops.

3. Step 3: Why other options fail

   Visited sets after generation are inefficient; pruning recursion by index doesn't prevent reuse; increasing recursion depth breaks problem constraints.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   BFS with state tracking handles reuse and duplicates [OK]

Hint: Use BFS with visited states to handle reuse [OK]

Common Mistakes:

• Trying to prune recursion by index only
• Ignoring duplicates generated by reuse