This article delves into advanced backtracking techniques for solving common algorithmic problems, specifically focusing on generating increasing subsequences and permutations, including handling duplicates.

Generating Increasing Subsequences (Problem 491)

Given an integer array, the task is to find all increasing subsequences with a length of atleast two. It's crucial to note that the original array must not be sorted, as sorting would inherently produce all increasing subsequences.

The core challenge lies in avoiding duplicate subsequences. Unlike problems where sorting simplifies deduplication, here we must manage duplicates within the backtracking process itself.

Backtracking Framework:

1. Recursive Function Parameters: To build subsequences, we need to track the starting index for the next element to maintain the order and prevent reuse of the same element within a single subsequence path. The path vector stores the current subsequence being built, and startIndex indicates where to begin the next search.

   vector<vector<int>> result;
   vector<int> path;
   void backtrack(vector<int>& nums, int startIndex)
   

2. Base Case: Subsequences of length greater than one are valid results. However, unlike some backtracking problems, we don't necessarily return immediately after finding a valid subsequence because we need to explore all possible extensions from that point.

   if (path.size() > 1) {
       result.push_back(path);
       // Do not return; continue exploring extensions.
   }
   

3. Recursive Step: The key to handling duplicates at the same level of recursion is to use a set (unordered_set) to keep track of elements already considered within the current recursive call's loop. If an element is encountered that is smaller than the last element in path (violating the increasing property) or has already been used in the current level, it's skipped.

   unordered_set<int> levelElements;
   for (int i = startIndex; i < nums.size(); ++i) {
       // Skip if current element violates increasing order or is a duplicate at this level.
       if ((!path.empty() && nums[i] < path.back()) || levelElements.count(nums[i])) {
           continue;
       }
       levelElements.insert(nums[i]); // Mark element as used for this level.
       path.push_back(nums[i]);
       backtrack(nums, i + 1);
       path.pop_back(); // Backtrack.
   }
   

   The unordered_set is local to each recursive call, ensuring it only manages duplicates within that specific level of the recursion tree. This approach effectively prunes redundant branches.

Full Implementation (Increasing Subsequences):

#include <vector>
#include <unordered_set>

class Solution {
private:
    std::vector<std::vector<int>> results;
    std::vector<int> currentPath;

    void backtrackHelper(std::vector<int>& nums, int startIndex) {
        if (currentPath.size() > 1) {
            results.push_back(currentPath);
        }

        std::unordered_set<int> usedInLevel;
        for (int i = startIndex; i < nums.size(); ++i) {
            if ((!currentPath.empty() && nums[i] < currentPath.back()) || usedInLevel.count(nums[i])) {
                continue;
            }
            usedInLevel.insert(nums[i]);
            currentPath.push_back(nums[i]);
            backtrackHelper(nums, i + 1);
            currentPath.pop_back();
        }
    }

public:
    std::vector<std::vector<int>> findSubsequences(std::vector<int>& nums) {
        results.clear();
        currentPath.clear();
        backtrackHelper(nums, 0);
        return results;
    }
};

Generating All Permutations (Problem 46)

For a sequence without duplicate numbers, the goal is to find all possible orderings (permutations).

Backtracking Framework:

1. Recursive Function Parameters: Unlike subsequences, permutations are order-sensitive. Each element can be reused across different permutation branches. Therefore, we don't use startIndex to limit the search range. Instead, a boolean array used tracks which elements are currently included in the path for the specific permutation being built.

   std::vector<std::vector<int>> permutations;
   std::vector<int> currentPermutation;
   void backtrack(std::vector<int>& nums, std::vector<bool>& used)
   

2. Base Case: A complete permutation is found when the currentPermutation vector reaches the same size as the input nums vector.

   if (currentPermutation.size() == nums.size()) {
       permutations.push_back(currentPermutation);
       return;
   }
   

3. Recursive Step: Iterate through all numbers in nums. If a number hasn't been used in the current permutation (!used[i]), mark it as used, add it to currentPermutation, recurse, and then backtrack by removing it and marking it as unused.

   for (int i = 0; i < nums.size(); ++i) {
       if (used[i]) continue;
       used[i] = true;
       currentPermutation.push_back(nums[i]);
       backtrack(nums, used);
       currentPermutation.pop_back();
       used[i] = false;
   }
   

Full Implementation (All Permutations):

#include <vector>
#include <numeric>

class Solution {
private:
    std::vector<std::vector<int>> allPermutations;
    std::vector<int> currentPermutation;

    void backtrackHelper(std::vector<int>& nums, std::vector<bool>& elementUsed) {
        if (currentPermutation.size() == nums.size()) {
            allPermutations.push_back(currentPermutation);
            return;
        }

        for (int i = 0; i < nums.size(); ++i) {
            if (elementUsed[i]) continue;
            elementUsed[i] = true;
            currentPermutation.push_back(nums[i]);
            backtrackHelper(nums, elementUsed);
            currentPermutation.pop_back();
            elementUsed[i] = false;
        }
    }

public:
    std::vector<std::vector<int>> permute(std::vector<int>& nums) {
        allPermutations.clear();
        currentPermutation.clear();
        std::vector<bool> elementUsed(nums.size(), false);
        backtrackHelper(nums, elementUsed);
        return allPermutations;
    }
};

Generating Unique Permutations (Problem 47)

This problem extends permutation generation to arrays that may contain duplicate numbers. The goal is to produce only unique permutations.

Key Strategy: Sorting and Conditional Skipping:

To efficiently handle duplicates, the input array nums must first be sorted. This allows us to identify adjacent duplicate elements. The backtracking logic then incorporates a condition to skip processing a duplicate element if its preceding identical element was not used in the current recursive path. This prevents generating redundant permutations.

Backtracking Logic (with Deduplication):

1. Sort Input: std::sort(nums.begin(), nums.end());
2. Recursive Parameters: Similar to Problem 46, we use currentPermutation and elementUsed.
3. Base Case: Same as Problem 46.
4. Recursive Step with Deduplication: The core modification is the condition within the loop: if (i > 0 && nums[i] == nums[i-1] && !elementUsed[i-1]) continue; This condition ensures that if the current element nums[i] is the same as the previous one nums[i-1], we only consider nums[i] if nums[i-1] has already been used in the current path. If nums[i-1] was not used (meaning it was considered and then backtracked from in the same level), we skip nums[i] to avoid duplicate permutations originating from swapping identical elements.

Full Implementation (Unique Permutations):

#include <vector>
#include <algorithm>
#include <numeric>

class Solution {
private:
    std::vector<std::vector<int>> uniquePermutations;
    std::vector<int> currentPermutation;

    void backtrackHelper(std::vector<int>& nums, std::vector<bool>& elementUsed) {
        if (currentPermutation.size() == nums.size()) {
            uniquePermutations.push_back(currentPermutation);
            return;
        }

        for (int i = 0; i < nums.size(); ++i) {
            // Skip if element is already used.
            if (elementUsed[i]) continue;
            // Skip duplicates: if current element is same as previous, and previous was NOT used (backtracked from).
            if (i > 0 && nums[i] == nums[i - 1] && !elementUsed[i - 1]) {
                continue;
            }

            elementUsed[i] = true;
            currentPermutation.push_back(nums[i]);
            backtrackHelper(nums, elementUsed);
            currentPermutation.pop_back();
            elementUsed[i] = false;
        }
    }

public:
    std::vector<std::vector<int>> permuteUnique(std::vector<int>& nums) {
        uniquePermutations.clear();
        currentPermutation.clear();
        std::sort(nums.begin(), nums.end()); // Crucial for duplicate handling.
        std::vector<bool> elementUsed(nums.size(), false);
        backtrackHelper(nums, elementUsed);
        return uniquePermutations;
    }
};