Subsets and Backtracking, Coding Interview Pattern
Tags: coding, algorithms, dsa, interview
Published: 2024-07-01 19:14:35

## Subsets

The Subsets technique is a fundamental approach used to solve problems involving the generation and manipulation of subsets from a given set of elements. This technique is particularly useful in scenarios where we need to explore all possible combinations of a set, such as in problems related to combinatorics, optimization, and decision-making. By systematically generating all subsets, we can address a wide range of problems, from finding power sets to solving subset sum challenges. This guide covers the core concepts of the Subsets technique, its applications in various problem domains, and practical strategies for implementing subset generation algorithms efficiently.

### Subsets
`This question is part of Leetcode problems, question no. 78.`

Here's the Solution class for the "Subsets" problem in C++:

```cpp
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> current;
        backtrack(nums, 0, current, result);
        return result;
    }
    
    void backtrack(vector<int>& nums, int start, vector<int>& current, vector<vector<int>>& result) {
        result.push_back(current);
        for (int i = start; i < nums.size(); ++i) {
            current.push_back(nums[i]);
            backtrack(nums, i + 1, current, result);
            current.pop_back();
        }
    }
};
```

### Permutations
`This question is part of Leetcode problems, question no. 46.`

Here's the Solution class for the "Permutations" problem in C++:

```cpp
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> current;
        vector<bool> used(nums.size(), false);
        backtrack(nums, used, current, result);
        return result;
    }
    
    void backtrack(vector<int>& nums, vector<bool>& used, vector<int>& current, vector<vector<int>>& result) {
        if (current.size() == nums.size()) {
            result.push_back(current);
            return;
        }
        
        for (int i = 0; i < nums.size(); ++i) {
            if (used[i]) continue;
            used[i] = true;
            current.push_back(nums[i]);
            backtrack(nums, used, current, result);
            current.pop_back();
            used[i] = false;
        }
    }
};
```

### Letter Combinations of a Phone Number
`This question is part of Leetcode problems, question no. 17.`

Here's the Solution class for the "Letter Combinations of a Phone Number" problem in C++:

```cpp
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        
        vector<string> result;
        string current;
        vector<string> mapping = {
            "",    "",    "abc",  "def", "ghi", "jkl",
            "mno", "pqrs", "tuv", "wxyz"
        };
        
        backtrack(digits, 0, current, result, mapping);
        return result;
    }
    
    void backtrack(const string& digits, int index, string& current, vector<string>& result, const vector<string>& mapping) {
        if (index == digits.size()) {
            result.push_back(current);
            return;
        }
        
        string letters = mapping[digits[index] - '0'];
        for (char letter : letters) {
            current.push_back(letter);
            backtrack(digits, index + 1, current, result, mapping);
            current.pop_back();
        }
    }
};
```

### Generate Parentheses
`This question is part of Leetcode problems, question no. 22.`

Here's the Solution class for the "Generate Parentheses" problem in C++:

```cpp
class Solution {
public:
    vector<string> generateParentheses(int n) {
        vector<string> result;
        string current;
        backtrack(result, current, 0, 0, n);
        return result;
    }
    
    void backtrack(vector<string>& result, string& current, int open, int close, int max) {
        if (current.size() == max * 2) {
            result.push_back(current);
            return;
        }
        
        if (open < max) {
            current.push_back('(');
            backtrack(result, current, open + 1, close, max);
            current.pop_back();
        }
        if (close < open) {
            current.push_back(')');
            backtrack(result, current, open, close + 1, max);
            current.pop_back();
        }
    }
};
```

### Combination Sum
`This question is part of Leetcode problems, question no. 39.`

Here's the Solution class for the "Combination Sum" problem in C++:

```cpp
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> current;
        backtrack(candidates, target, 0, current, result);
        return result;
    }
    
    void backtrack(vector<int>& candidates, int target, int start, vector<int>& current, vector<vector<int>>& result) {
        if (target == 0) {
            result.push_back(current);
            return;
        }
        
        for (int i = start; i < candidates.size(); ++i) {
            if (candidates[i] <= target) {
                current.push_back(candidates[i]);
                backtrack(candidates, target - candidates[i], i, current, result);
                current.pop_back();
            }
        }
    }
};
```