子集和问题

在**子集和问题**中，给定一个包含一些非负整数元素的集合。同时还提供一个和值，我们的任务是找到给定集合的所有可能的子集，其元素之和与给定的和值相同。

**集合：**在数学术语中，**集合**被定义为相似类型对象的集合。集合的实体或对象必须通过相同的规则相互关联。

**子集：**假设有两个集合，即集合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）包含到空集中。
如果子集等于和值，则将其标记为解的一部分。
如果子集不是解并且小于和值，则向子集中添加下一个元素，直到找到有效的解。
现在，转到集合中的下一个元素并检查另一个解，直到所有组合都已尝试过。

示例

在本示例中，我们将说明如何在各种编程语言中解决子集和问题。

C C++ Java Python

Open Compiler

#include <stdio.h>
#define SIZE 7
void displaySubset(int subSet[], int size) {
   for(int i = 0; i < size; i++) {
      printf("%d  ", subSet[i]);
   }
   printf("\n");
}
void subsetSum(int set[], int subSet[], int n, int subSize, int total, int nodeCount ,int sum) {
   if( total == sum) {
      //print the subset 
      displaySubset(subSet, subSize);  
      //for other subsets
      if (subSize != 0)
         subsetSum(set,subSet,n,subSize-2,total-set[nodeCount],nodeCount+1,sum);     
      return;
   }else {
      //find node along breadth 
      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) {
   //create subset array to pass parameter of 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;
}

Open Compiler

#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) {
      //print the subset 
      displaySubset(subSet, subSize);  
      //for other subsets
      subsetSum(set, subSet, n, subSize-1, total-set[nodeCount], nodeCount+1,sum);     
      return;
   }else {
      //find node along breadth 
      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) {
   //create subset array to pass parameter of 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);
}

Open Compiler

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) {
         //print the subset 
         displaySubset(subSet, subSize);  
         //for other subsets
         if (subSize != 0)
            subsetSum(set,subSet,n,subSize-1,total-set[nodeCount],nodeCount+1,sum);     
         return;
      } else {
         //find node along breadth 
         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);    
         }
      }
   }
   static void findSubset(int set[], int size, int sum) {
      //create subset array to pass parameter of 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);
   }
}

Open Compiler

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:
        #print the subset 
        displaySubset(subSet, subSize)
        #for other subsets
        if subSize != 0:
            subsetSum(set, subSet, n, subSize-1, total-set[nodeCount], nodeCount+1, sum)
        return
    else:
        #find node along breadth 
        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):
    #create subset array to pass parameter of 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

打印页面