Day 19 – Recursion, Backtracking, and Math Logic

1. Subset Sum (Leetcode 78: Subsets)

Problem: Return all possible subsets (the power set) of a given array of distinct integers.

Intuition: At each index, we have two choices: include or exclude the current element.

void solve(int i, vector<int>& nums, vector<int>& temp, vector<vector<int>>& ans) {
    if (i == nums.size()) {
        ans.push_back(temp);
        return;
    }
    temp.push_back(nums[i]);
    solve(i + 1, nums, temp, ans);
    temp.pop_back();
    solve(i + 1, nums, temp, ans);
}

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> ans;
    vector<int> temp;
    solve(0, nums, temp, ans);
    return ans;
}
// TC: O(2^n) subsets * O(n) per subset = O(n * 2^n)
// SC: O(n) recursion + O(n * 2^n) output

---

2. Subset Sum 2 (Leetcode 90: Subsets II)

Problem: Like Subset Sum, but input can have duplicates, and result should have unique subsets.

Intuition: Sort array first. If we pick an element, skip all consecutive duplicates in the same recursion level.

void solve(int start, vector<int>& nums, vector<int>& temp, vector<vector<int>>& ans) {
    ans.push_back(temp);
    for (int i = start; i < nums.size(); i++) {
        if (i > start && nums[i] == nums[i - 1]) continue;
        temp.push_back(nums[i]);
        solve(i + 1, nums, temp, ans);
        temp.pop_back();
    }
}

vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> ans;
    vector<int> temp;
    solve(0, nums, temp, ans);
    return ans;
}
// TC: O(2^n)
// SC: O(n * 2^n) output + O(n) recursion

---

3. Combination Sum 1 (Leetcode 39)

Problem: Given array of candidates (no duplicates), and target. You can reuse elements. Find combinations that sum to target.

Intuition: Backtrack by including current element (can repeat), or move to next. Stop if sum exceeds target.

void dfs(int i, int target, vector<int>& temp, vector<vector<int>>& ans, vector<int>& candidates) {
    if (target == 0) {
        ans.push_back(temp);
        return;
    }
    if (i == candidates.size() || target < 0) return;

    temp.push_back(candidates[i]);
    dfs(i, target - candidates[i], temp, ans, candidates);
    temp.pop_back();

    dfs(i + 1, target, temp, ans, candidates);
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> ans;
    vector<int> temp;
    dfs(0, target, temp, ans, candidates);
    return ans;
}
// TC: O(2^t) where t = target, since each element can be reused
// SC: O(target) recursion + output

---

4. Combination Sum 2 (Leetcode 40)

Problem: Each number can be used only once, and array may contain duplicates.

Intuition: Sort the array. At each recursion level, skip duplicates after using one instance of a number.

void dfs(int start, int target, vector<int>& temp, vector<vector<int>>& ans, vector<int>& candidates) {
    if (target == 0) {
        ans.push_back(temp);
        return;
    }

    for (int i = start; i < candidates.size(); ++i) {
        if (i > start && candidates[i] == candidates[i - 1]) continue;
        if (candidates[i] > target) break;
        temp.push_back(candidates[i]);
        dfs(i + 1, target - candidates[i], temp, ans, candidates);
        temp.pop_back();
    }
}

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end());
    vector<vector<int>> ans;
    vector<int> temp;
    dfs(0, target, temp, ans, candidates);
    return ans;
}
// TC: O(2^n)
// SC: O(n) recursion + output

---

5. Palindrome Partitioning (Leetcode 131)

Problem: Partition a string such that every substring is a palindrome.

Intuition: Backtrack while checking palindromic substrings. If valid, recurse on remaining string.

bool isPalindrome(string& s, int l, int r) {
    while (l < r) {
        if (s[l++] != s[r--]) return false;
    }
    return true;
}

void dfs(int start, string& s, vector<string>& temp, vector<vector<string>>& ans) {
    if (start == s.size()) {
        ans.push_back(temp);
        return;
    }

    for (int end = start; end < s.size(); ++end) {
        if (isPalindrome(s, start, end)) {
            temp.push_back(s.substr(start, end - start + 1));
            dfs(end + 1, s, temp, ans);
            temp.pop_back();
        }
    }
}

vector<vector<string>> partition(string s) {
    vector<vector<string>> ans;
    vector<string> temp;
    dfs(0, s, temp, ans);
    return ans;
}
// TC: O(2^n * n) — exponential for combinations, n for checking palindrome
// SC: O(n) recursion + output

---

6. Permutation Sequence (Leetcode 60)

Brute-force:

Idea: Generate all permutations using STL or backtracking and return the kth.

string getPermutation(int n, int k) {
    vector<int> nums;
    for (int i = 1; i <= n; i++) nums.push_back(i);
    vector<string> perms;

    do {
        string s;
        for (int i : nums) s += to_string(i);
        perms.push_back(s);
    } while (next_permutation(nums.begin(), nums.end()));

    return perms[k - 1];
}
// TC: O(n! * n)
// SC: O(n!)

Optimal (Math based):

Intuition: Use factorial logic. For each digit position, decide which number it should be.

string getPermutation(int n, int k) {
    vector<int> nums;
    for (int i = 1; i <= n; i++) nums.push_back(i);

    int fact = 1;
    for (int i = 1; i < n; i++) fact *= i;

    k -= 1; // 0-indexed
    string ans = "";

    while (!nums.empty()) {
        int idx = k / fact;
        ans += to_string(nums[idx]);
        nums.erase(nums.begin() + idx);
        if (nums.empty()) break;
        k %= fact;
        fact /= nums.size();
    }
    return ans;
}
// TC: O(n^2) due to erase in vector
// SC: O(n)