Problem 491: Increasing Subsequences

Given an enteger array nums, find all strictly increasing subsequences that contain at least two elements. Return the solution without duplicate subsequences.

The key challenge here is that we cannot sort the original array, as sorting would transfrom every subsequence into an increasing one, defeating the purpose of the problem.

class Solution {
private:
    vector<int> current;
    vector<vector<int>> answers;
    
public:
    void dfs(const vector<int>& nums, int start) {
        if (current.size() > 1) {
            answers.push_back(current);
        }
        
        int seen[201] = {0};  // Range -100 to 100
        
        for (int i = start; i < nums.size(); i++) {
            // Skip if not increasing or already used at this level
            if ((!current.empty() && nums[i] < current.back()) || 
                seen[nums[i] + 100] == 1) {
                continue;
            }
            
            current.push_back(nums[i]);
            seen[nums[i] + 100] = 1;
            dfs(nums, i + 1);
            current.pop_back();
        }
    }
    
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        dfs(nums, 0);
        return answers;
    }
};

Key Considerations:

• The seen[201] array handles the value range from -100 to 100
• The array cannot be sorted before processing
• The seen array must be recreated at each recursion level to handle tree-level deduplication

---

Problem 46: Permutations

Generate all possible permutations of an array containing distinct integers.

class Solution {
private:
    vector<int> current;
    vector<vector<int>> answers;
    
public:
    void dfs(const vector<int>& nums, vector<bool>& visited) {
        if (current.size() == nums.size()) {
            answers.push_back(current);
            return;
        }
        
        for (int i = 0; i < nums.size(); i++) {
            if (visited[i]) {
                continue;
            }
            
            current.push_back(nums[i]);
            visited[i] = true;
            dfs(nums, visited);
            visited[i] = false;
            current.pop_back();
        }
    }
    
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> visited(nums.size(), false);
        dfs(nums, visited);
        return answers;
    }
};

Key Considerations:

• Use a visited array indexed by position rather than value
• Each element is used exactly once per permutation
• Backtrack after each recursive call to explore other branches

---

Problem 47: Permutations II

Generate all unique permutations when the input array may contain duplicates.

class Solution {
private:
    vector<int> current;
    vector<vector<int>> answers;
    
public:
    void dfs(const vector<int>& nums, vector<bool>& visited) {
        if (current.size() == nums.size()) {
            answers.push_back(current);
            return;
        }
        
        for (int i = 0; i < nums.size(); i++) {
            // Skip duplicates at tree level (same level previous element not used)
            if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
                continue;
            }
            
            if (!visited[i]) {
                current.push_back(nums[i]);
                visited[i] = true;
                dfs(nums, visited);
                visited[i] = false;
                current.pop_back();
            }
        }
    }
    
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<bool> visited(nums.size(), false);
        sort(nums.begin(), nums.end());
        dfs(nums, visited);
        return answers;
    }
};

Key Considerations:

• Sorting is required to group duplicates together
• The condition !visited[i-1] checks if we're at the tree level (not branch level)
• Use !visited[i-1] for tree-level deduplication to avoid generating duplicate permutations

---

Summary of Deduplication Strategies

Scenario	Condition	Purpose
Tree-level (same depth)	used[i-1] == false	Skip duplicate branches at current level
Branch-level (deeper levels)	used[i-1] == true	Skip duplicate paths in recursion tree