Skip to content

Backtracking Subset

Table of Contents

78. Subsets

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

1286. Iterator for Combination

494. Target Sum

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

1239. Maximum Length of a Concatenated String with Unique Characters

2212. Maximum Points in an Archery Competition

1255. Maximum Score Words Formed by Letters

2151. Maximum Good People Based on Statements

2597. The Number of Beautiful Subsets

  • LeetCode | 力扣

  • Tags: Array, Hash Table, Math, Dynamic Programming, Backtracking, Sorting, Combinatorics

#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

1601. Maximum Number of Achievable Transfer Requests

1617. Count Subtrees With Max Distance Between Cities

320. Generalized Abbreviation

254. Factor Combinations

39. Combination Sum

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]]

Comments