Subset Sum - Backtracking phần 2

    Tiếp tục về đệ quy quay lui (backtracking), hôm nay chúng ta đi giải quyết bài toán Subset Sum (tìm tập hợp con có tổng bằng k). Bài toán đặt ra là: cho mảng arr[] = {1, 2, 3} và tổng k = 4, ta chia bài toán thành 4 trường hợp

1. Subset Sum 

    Ta quan tâm đến cả thứ tự các phần tử trong mảng, tức là {1, 2} và {2, 1} sẽ coi là hai cách chọn khác nhau.

1.1. Các phần tử trong mảng được sử dụng thoải mái

int arr[MAX];
void Try(int subSum, int sum, vector<int> x){
  if(subSum == sum){
    count++;
    for(int i = 0; i < x.size(); i++)
      cout << x[i] << " ";
    cout << endl;
    return;
  }
  for(int i = 0; i < n; i++){
    if(subSum + arr[i] > sum)
      continue;
    
    x.push_back(arr[i]);
    Try(subSum + arr[i], sum, x);
    x.pop_back();
  }
}

1.2. Các phần tử trong mảng là duy nhất

int arr[MAX], n, count = 0;
bool visited[MAX];
void Try(int subSum, int sum, vector<int> &x){
  if(subSum == sum)
  {
    count++;
    for(int i = 0; i < x.size(); i++)
      cout << x[i] << " ";
    cout << endl;
    return;
  }
  for(int i = l; i < n; i++){
    if(subSum + arr[i] > sum)
      continue;
    if(visited[i])
      continue;

    visited[i] = true;
    x.push_back(arr[i]);
    Try(subSum + arr[i], sum, x);
    x.pop_back();
    visited[i] = false;
  }
}

2. Unique Subset Sum

    Thứ tự các phần tử trong mảng là không quan trọng, tức là {1, 2} và {2, 1} được coi là như nhau.

2.1. Các phần tử trong mảng được sử dụng thoải mái

int arr[MAX], cnt = 0;
vector<int> x;

void Try(int arr[], int l, int n, int subSum, int sum){
  if(subSum == sum){
    cnt++;
    for(int i = 0; i < x.size(); i++)
      cout << x[i] << " ";
    cout << endl;
    return;
  }
  for(int i = l; i < n; i++){
    if(subSum + arr[i] > sum)
      continue;
    
    if(i && arr[i] == arr[i - 1] && i > l)
      continue;
    
    x.push_back(arr[i]);
    Try(arr, i, n, subSum + arr[i], sum);
    x.pop_back();
  }
}
int UniqueCombinationSum(int arr[], int n, int sum){
  sort(arr, arr + n);
  Try(arr, 0, n, 0, sum);

  return cnt;
}

2.2. Các phần tử trong mảng là duy nhất

int arr[MAX], cnt = 0;
vector<int> x;

void Try(int arr[], int l, int n, int subSum, int sum){
  if(subSum == sum)
  {
    cnt++;
    for(int i = 0; i < x.size(); i++)
      cout << x[i] << " ";
    cout << endl;
    return;
  }
  for(int i = l; i < n; i++){
    if(subSum + arr[i] > sum)
      continue;
    if(i && arr[i] == arr[i - 1] && i > l)
      continue;
    x.push_back(arr[i]);
    Try(arr, i + 1, n, subSum + arr[i], sum);
    x.pop_back();
  }
}
int UniqueCombinationSum(int arr[], int n, int sum){
  sort(arr, arr + n);
  Try(arr, 0, n, 0, sum);

  return cnt;
}

Hẹn gặp lại mọi người ở bài viết tiếp theo!