Bài toán tổng tập hợp con

Trong bài toán này, có một tập hợp đã cho với một số phần tử nguyên. Và một số giá trị khác cũng được cung cấp, chúng ta phải tìm một tập hợp con của tập hợp đã cho có tổng bằng với giá trị tổng đã cho.

Ở đây, phương pháp backtracking được sử dụng để cố gắng chọn một tập hợp con hợp lệ khi một mục không hợp lệ, chúng tôi sẽ quay lại để lấy tập hợp con trước đó và thêm một phần tử khác để có được giải pháp.

Đầu vào và Đầu ra

Input:
This algorithm takes a set of numbers, and a sum value.
The Set: {10, 7, 5, 18, 12, 20, 15}
The sum Value: 35
Output:
All possible subsets of the given set, where sum of each element for every subsets is same as the given sum value.
{10,  7,  18}
{10,  5,  20}
{5,  18,  12}
{20,  15}

Thuật toán

subsetSum(set, subset, n, subSize, total, node, sum)

Đầu vào - Tập hợp và tập hợp con đã cho, kích thước của tập hợp và tập hợp con, tổng của tập hợp con, số phần tử trong tập hợp con và tổng đã cho.

Đầu ra - Tất cả các tập hợp con có thể có tổng bằng tổng đã cho.

Begin
   if total = sum, then
      display the subset
      //go for finding next subset
      subsetSum(set, subset, , subSize-1, total-set[node], node+1, sum)
      return
   else
      for all element i in the set, do
         subset[subSize] := set[i]
         subSetSum(set, subset, n, subSize+1, total+set[i], i+1, sum)
      done
End

Ví dụ

#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);     //print the subset
      subsetSum(set,subSet,n,subSize-1,total-set[nodeCount],nodeCount+1,sum);     //for other subsets
      return;
   }else {
      for( int i = nodeCount; i < n; i++ ) {     //find node along breadth
         subSet[subSize] = set[i];
         subsetSum(set,subSet,n,subSize+1,total+set[i],i+1,sum);     //do for next node in depth
      }
   }
}

void findSubset(int set[], int size, int sum) {
   int *subSet = new int[size];     //create subset array to pass parameter of subsetSum
   subsetSum(set, subSet, size, 0, 0, 0, sum);
   delete[] subSet;
}

int main() {
   int weights[] = {10, 7, 5, 18, 12, 20, 15};
   int size = 7;
   findSubset(weights, size, 35);
}

Đầu ra