Subsets and Backtracking, Coding Interview Pattern

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++:

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++:

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++:

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++:

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++:

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();
            }
        }
    }
};