Bài toán Tổng tập con (Subset Sum Problem)

Giới thiệu

Cho tập số nguyên và giá trị mục tiêu. Tìm tập con có tổng bằng giá trị mục tiêu.

Dùng backtracking: thử chọn phần tử, nếu tổng vượt quá hoặc không dẫn đến lời giải thì quay lui.

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

Đầu vào: Tập: {10, 7, 5, 18, 12, 20, 15}, Tổng mục tiêu: 35
Đầu ra: Các tập con có tổng = 35:
{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 gốc, tập con, kích thước, tổng hiện tại, nút hiện tại, tổng mục tiêu.

Đầu ra: Tất cả tập con có tổng = sum.

Begin
  nếu total = sum thì
    hiển thị subset
    subsetSum(set, subset, n, subSize-1, total-set[node], node+1, sum)
    return
  ngược lại
    với mọi phần tử i trong set làm:
      subset[subSize] := set[i]
      subsetSum(set, subset, n, subSize+1, total+set[i], i+1, sum)
    done
End

Ví dụ (C++)

#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];
      subsetSum(set, subSet, n, subSize+1, total+set[i], i+1, sum);
    }
  }
}

void findSubset(int set[], int size, int sum) {
  int *subSet = new int[size];
  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);
}

Kết quả đầu ra

10   7   18
10   5   20
5   18   12
20   15