이 문제에는 일부 정수 요소가 포함된 집합이 있습니다. 그리고 또 다른 어떤 값도 제공되는데, 주어진 합 값과 합이 같은 주어진 집합의 부분집합을 찾아야 합니다.
여기서 역추적 접근 방식은 항목이 유효하지 않을 때 유효한 하위 집합을 선택하는 데 사용됩니다. 이전 하위 집합을 가져오기 위해 역추적하고 솔루션을 얻기 위해 다른 요소를 추가합니다.
입력 및 출력
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}
알고리즘
subsetSum(set, subset, n, subSize, total, node, sum)
입력 - 주어진 집합과 부분 집합, 집합과 부분 집합의 크기, 부분 집합의 합계, 부분 집합의 요소 수 및 주어진 합계.
출력 - 합계가 주어진 합계와 동일한 모든 가능한 하위 집합입니다.
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
예
#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); }
출력
10 7 18 10 5 20 5 18 12 20 15