Backtracking Subset¶

Table of Contents¶

78. Subsets¶

LeetCode | LeetCode CH (Medium)
Tags: array, backtracking, bit manipulation

78. Subsets - Python Solution

from typing import List


# Iterative Inclusion Backtracking
def subsets_iterative_inclusion(nums: List[int]) -> List[List[int]]:
    n = len(nums)
    res, path = [], []

    def dfs(i):
        res.append(path.copy())

        for j in range(i, n):
            path.append(nums[j])
            dfs(j + 1)
            path.pop()

    dfs(0)

    return res


# Binary Decision Backtracking
def subsets_binary_decision(nums: List[int]) -> List[List[int]]:
    n = len(nums)
    res, path = [], []

    def dfs(i):
        if i == n:
            res.append(path.copy())
            return

        # Exclude
        dfs(i + 1)

        # Include
        path.append(nums[i])
        dfs(i + 1)
        path.pop()

    dfs(0)

    return res


print(subsets_iterative_inclusion([1, 2, 3]))
# [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
print(subsets_binary_decision([1, 2, 3]))
# [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

784. Letter Case Permutation¶

LeetCode | LeetCode CH (Medium)
Tags: string, backtracking, bit manipulation

1286. Iterator for Combination¶

LeetCode | LeetCode CH (Medium)
Tags: string, backtracking, design, iterator

494. Target Sum¶

LeetCode | LeetCode CH (Medium)
Tags: array, dynamic programming, backtracking

494. Target Sum - Python Solution

from typing import List


def findTargetSumWays(nums: List[int], target: int) -> int:

    totalSum = sum(nums)

    if abs(target) > totalSum:
        return 0
    if (target + totalSum) % 2 == 1:
        return 0

    targetSum = (target + totalSum) // 2
    dp = [0] * (targetSum + 1)
    dp[0] = 1

    for i in range(len(nums)):
        for j in range(targetSum, nums[i] - 1, -1):
            dp[j] += dp[j - nums[i]]

    return dp[targetSum]


nums = [1, 1, 1, 1, 1]
target = 3
print(findTargetSumWays(nums, target))  # 5

2397. Maximum Rows Covered by Columns¶

LeetCode | LeetCode CH (Medium)
Tags: array, backtracking, bit manipulation, matrix, enumeration

1239. Maximum Length of a Concatenated String with Unique Characters¶

LeetCode | LeetCode CH (Medium)
Tags: array, string, backtracking, bit manipulation

2212. Maximum Points in an Archery Competition¶

LeetCode | LeetCode CH (Medium)
Tags: array, backtracking, bit manipulation, enumeration

1255. Maximum Score Words Formed by Letters¶

LeetCode | LeetCode CH (Hard)
Tags: array, string, dynamic programming, backtracking, bit manipulation, bitmask

2151. Maximum Good People Based on Statements¶

LeetCode | LeetCode CH (Hard)
Tags: array, backtracking, bit manipulation, enumeration

2597. The Number of Beautiful Subsets¶

LeetCode | LeetCode CH (Medium)

Tags: array, hash table, math, dynamic programming, backtracking, sorting, combinatorics

2597. The Number of Beautiful Subsets - C++ Solution

#include <functional>
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
   public:
    int beautifulSubsets(vector<int>& nums, int k) {
        int res = 0;
        unordered_map<int, int> cnt;

        auto dfs = [&](auto&& self, int i) -> void {
            if (i == (int)nums.size()) {
                res++;
                return;
            }
            self(self, i + 1);  // Skip nums[i]
            int x = nums[i];
            if (cnt[x - k] == 0 && cnt[x + k] == 0) {
                cnt[x]++;
                self(self, i + 1);  // Include nums[i]
                cnt[x]--;           // Backtrack
            }
        };

        dfs(dfs, 0);

        return res - 1;
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1, 2, 3, 4};
    int k = 1;
    cout << sol.beautifulSubsets(nums, k) << endl;
    return 0;
}

2959. Number of Possible Sets of Closing Branches¶

LeetCode | LeetCode CH (Hard)
Tags: bit manipulation, graph, heap priority queue, enumeration, shortest path

1601. Maximum Number of Achievable Transfer Requests¶

LeetCode | LeetCode CH (Hard)
Tags: array, backtracking, bit manipulation, enumeration

1617. Count Subtrees With Max Distance Between Cities¶

LeetCode | LeetCode CH (Hard)
Tags: dynamic programming, bit manipulation, tree, enumeration, bitmask

320. Generalized Abbreviation¶

LeetCode | LeetCode CH (Medium)
Tags: string, backtracking, bit manipulation

254. Factor Combinations¶

LeetCode | LeetCode CH (Medium)
Tags: backtracking

39. Combination Sum¶

LeetCode | LeetCode CH (Medium)
Tags: array, backtracking

39. Combination Sum - Python Solution

from typing import List


def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
    n = len(candidates)
    res, path = [], []

    def dfs(total, start):
        if total > target:
            return
        if total == target:
            res.append(path.copy())
            return

        for i in range(start, n):
            total += candidates[i]
            path.append(candidates[i])
            dfs(total, i)
            total -= candidates[i]
            path.pop()

    dfs(0, 0)

    return res


if __name__ == "__main__":
    print(combinationSum([2, 3, 5], 8))
    # [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
    print(combinationSum([2, 3, 6, 7], 7))
    # [[2, 2, 3], [7]]