使用回溯法解决子集和问题

给定一个包含非负整数的 set[] 和一个目标值 sum，我们的任务是打印出该集合中所有加起来等于给定 sum 的子集。

示例：

> 输入： set[] = {1,2,1}, sum = 3

> 输出： [1,2],[2,1]

> 解释： 存在子集 [1,2] 和 [2,1]，它们的和为 3。

>

> 输入： set[] = {3, 34, 4, 12, 5, 2}, sum = 30

> 输出： []

> 解释： 没有子集的和等于 30。

子集和问题也可以看作是 0–1 背包问题 的一个特例。对于每一个元素，我们都有两种可能性：

• 将当前元素 包含 在子集中，并在剩余的 Sum 下对剩余元素进行递归。
• 从子集中 排除 当前元素，并对剩余元素进行递归。

最后，如果 Sum 变为 0，那么我们就打印当前子集的元素。递归的 基准情况 是当 没有元素剩余，或者 sum 变为 负数 时，此时直接返回即可。

!<a href="https://media.geeksforgeeks.org/wp-content/uploads/20230717175725/subsetSumFinal.webp">subsetSumFinal

上述方法的实现：

C++

#include 
using namespace std;

// 打印所有子集，如果 set[] 中至少存在一个子集
// 其和等于给定的 sum
bool flag = 0;
void PrintSubsetSum(int i, int n, int set[], int targetSum,
                    vector& subset)
{
    // 如果 targetSum 为零，则存在一个
    // 子集。
    if (targetSum == 0) {

        // 打印有效的子集
        flag = 1;
        cout << "[ ";
        for (int i = 0; i < subset.size(); i++) {
            cout << subset[i] << " ";
        }
        cout << "]";
        return;
    }

    if (i == n) {
        // 如果我们已经到达数组的末尾，则返回
        return;
    }

    // 不考虑当前元素
    PrintSubsetSum(i + 1, n, set, targetSum, subset);

    // 如果当前元素小于或等于 targetSum，则考虑它
    if (set[i] <= targetSum) {

        // 将当前元素加入子集
        subset.push_back(set[i]);

        // 递归调用以考虑当前元素
        PrintSubsetSum(i + 1, n, set, targetSum - set[i],
                       subset);

        // 在递归调用后移除元素，以恢复
        // 子集的原始配置
        subset.pop_back();
    }
}

// 主代码
int main()
{
    // 测试用例 1
    int set[] = { 1, 2, 1 };
    int sum = 3;
    int n = sizeof(set) / sizeof(set[0]);
    vector subset;
    cout << "Output 1:" << endl;
    PrintSubsetSum(0, n, set, sum, subset);
    cout << endl;
    flag = 0;
    // 测试用例 2
    int set2[] = { 3, 34, 4, 12, 5, 2 };
    int sum2 = 30;
    int n2 = sizeof(set) / sizeof(set[0]);
    vector subset2;
    cout << "Output 2:" << endl;
    PrintSubsetSum(0, n2, set2, sum2, subset2);
    if (!flag) {
        cout << "There is no such subset";
    }

    return 0;
}
// 此代码由 Hem Kishan 贡献

`

Java

import java.util.ArrayList;
import java.util.List;

public class SubsetSum {

    // 标志位，用于检查是否存在具有给定和的子集
    static boolean flag = false;

    // 如果 set[] 中至少存在一个子集的和等于给定的 sum，
    // 则打印所有子集
    static void printSubsetSum(int i, int n, int[] set,
                               int targetSum,
                               List subset)
    {
        // 如果 targetSum 为零，则存在一个子集。
        if (targetSum == 0) {
            // 打印一个有效的子集
            flag = true;
            System.out.print("[ ");
            for (int j = 0; j < subset.size(); j++) {
                System.out.print(subset.get(j) + " ");
            }
            System.out.print("]");
            return;
        }

        if (i == n) {
            // 如果我们已经到达数组的末尾，
            // 则返回
            return;
        }

        // 不考虑当前元素
        printSubsetSum(i + 1, n, set, targetSum, subset);

        // 如果当前元素小于或等于 targetSum，则考虑它
        if (set[i] <= targetSum) {
            // 将当前元素加入子集
            subset.add(set[i]);

            // 递归调用以考虑当前元素
            printSubsetSum(i + 1, n, set,
                           targetSum - set[i], subset);

            // 在递归调用后移除元素，以恢复
            // 子集的原始配置
            subset.remove(subset.size() - 1);