子集和问题
子集和问题
子集和问题中，给定一个包含非负整数元素的集合，并给出另一个和值，我们的任务是找出该集合中所有和值与给定和值相同的可能子集。
集合：用数学术语来说，集合被定义为相似类型对象的集合。集合中的实体或对象必须通过相同的规则相互关联。
子集：假设有两个集合，即集合 P 和集合 Q。集合 P 被称为集合 Q 的子集，仅当集合 P 的所有元素也属于集合 Q，反之亦然，这不一定成立。
输入输出场景
假设给定集合，其和为 -
Set = {1, 9, 7, 5, 18, 12, 20, 15}
sum value = 35
给定集合的所有可能子集，其中每个子集的每个元素的和与给定的和值相同，如下所示 −
{1 9 7 18}
{1 9 5 20}
{5 18 12}
回溯法求解子集和问题
在朴素方法求解子集和问题时，算法会生成所有可能的排列，然后逐一检查是否存在有效解。只要某个解满足约束条件，就将其标记为解的一部分。
在求解子集和问题时，回溯法用于选择有效子集。当某个元素无效时，我们将回溯以获取前一个子集，并添加另一个元素以获得解。
在最坏情况下，回溯法可能会生成所有组合，但通常情况下，它的性能优于朴素方法。
按照以下步骤使用回溯法求解子集和问题 −
首先，取一个空子集。
将下一个元素（索引 0 处的元素）添加到空集中。
如果子集等于和值，则将其标记为解的一部分。
如果子集不是解，且小于和值，则将下一个元素添加到子集中，直到找到有效解。
现在，移动到集合中的下一个元素并检查另一个解，直到尝试完所有组合。
示例
在此示例中，我们将说明如何在各种编程语言中解决子集和问题。
#include <stdio.h>
#define SIZE 7
void displaySubset(int subSet[], int size) {
for(int i = 0; i < size; i++) {
printf("%d ", subSet[i]);
}
printf("
");
}
void subsetSum(int set[], int subSet[], int n, int subSize, int total, int nodeCount ,int sum) {
if( total == sum) {
//打印子集
displaySubset(subSet, subSize);
//其他子集
if (subSize != 0)
subsetSum(set,subSet,n,subSize-2,total-set[nodeCount],nodeCount+1,sum);
return;
}else {
//沿宽度查找节点
for( int i = nodeCount; i < n; i++ ) {
subSet[subSize] = set[i];
//对下一个节点进行深度操作
subsetSum(set,subSet,n,subSize+1,total+set[i],i+1,sum);
}
}
}
void findSubset(int set[], int size, int sum) {
//创建子集数组来传递subsetSum的参数
int subSet[size];
subsetSum(set, subSet, size, 0, 0, 0, sum);
}
int main() {
int weights[] = {1, 9, 7, 5, 18, 12, 20, 15};
int size = SIZE;
findSubset(weights, size, 35);
return 0;
}
#include <iostream>
using namespace std;
void displaySubset(int subSet[], int size) {
for(int i = 0; i < size; i++) {
cout << subSet[i] << " ";
}
cout << endl;
}
void subsetSum(int set[], int subSet[], int n, int subSize, int total, int nodeCount, int sum) {
if( total == sum) {
//打印子集
displaySubset(subSet, subSize);
//对于其他子集
subsetSum(set, subSet, n, subSize-1, total-set[nodeCount], nodeCount+1,sum);
return;
}else {
//沿宽度查找节点
for( int i = nodeCount; i < n; i++ ) {
subSet[subSize] = set[i];
//do for next node in depth
subsetSum(set, subSet, n, subSize+1, total+set[i], i+1, sum);
}
}
}
void findSubset(int set[], int size, int sum) {
//创建子集数组来传递subsetSum的参数
int *subSet = new int[size];
subsetSum(set, subSet, size, 0, 0, 0, sum);
delete[] subSet;
}
int main() {
int weights[] = {1, 9, 7, 5, 18, 12, 20, 15};
int size = 7;
findSubset(weights, size, 35);
}
public class Main {
static void displaySubset(int subSet[], int size) {
for(int i = 0; i < size; i++) {
System.out.print(subSet[i] + " ");
}
System.out.println();
}
static void subsetSum(int set[], int subSet[], int n, int subSize, int total, int nodeCount ,int sum) {
if( total == sum) {
//打印子集
displaySubset(subSet, subSize);
//其他子集
if (subSize != 0)
subsetSum(set,subSet,n,subSize-1,total-set[nodeCount],nodeCount+1,sum);
return;
} else {
//沿宽度查找节点
for( int i = nodeCount; i < n; i++ ) {
subSet[subSize] = set[i];
//对下一个节点进行深度操作
subsetSum(set,subSet,n,subSize+1,total+set[i],i+1,sum);
}
}
}
static void findSubset(int set[], int size, int sum) {
//创建子集数组来传递 subsetSum 的参数
int subSet[] = new int[size];
subsetSum(set, subSet, size, 0, 0, 0, sum);
}
public static void main(String[] args) {
int weights[] = {1, 9, 7, 5, 18, 12, 20, 15};
int size = 7;
findSubset(weights, size, 35);
}
}
def displaySubset(subSet, size):
for i in range(size):
print(subSet[i], end=" ")
print()
def subsetSum(set, subSet, n, subSize, total, nodeCount, sum):
if total == sum:
#打印子集
displaySubset(subSet, subSize)
#对于其他子集
if subSize != 0:
subsetSum(set, subSet, n, subSize-1, total-set[nodeCount], nodeCount+1, sum)
return
else:
#沿宽度查找节点
for i in range(nodeCount, n):
subSet[subSize] = set[i]
#do for next node in depth
subsetSum(set, subSet, n, subSize+1, total+set[i], i+1, sum)
def findSubset(set, size, sum):
#创建子集数组来传递 subsetSum 的参数
subSet = [0]*size
subsetSum(set, subSet, size, 0, 0, 0, sum)
if __name__ == "__main__":
weights = [1, 9, 7, 5, 18, 12, 20, 15]
size = 7
findSubset(weights, size, 35)
输出
1 9 7 18 1 9 5 20 5 18 12
