Given an array a contains distinct positive integers, count how many combinations of integers in a add up to exactly sum
For example, given int[] a = {11, 3, 8} ; and sum = 11
You should output 2, because 11 == 11 and 3 + 8 == 11
This is typically a backtracking problem
Enumerate all the subsets of the given array to see how many of them match the condition
when you write backtracking procedure using recursion, please be careful of which condition do you
use to terminate the loop, in this code snippet, there two conditions,
1. sum == 0
2. t == a.Length
and when t == a.Length, we might be got an solution yet, don't forget this case.
Backtracking
Code
recursive way
Code
C法
#include<stdio.h> #include<stdlib.h> int count = 0; // number of solutions /* * array - positive numbers * n - element count in array * sum - pair of sum * t - recursion deep */ void find_combinations(int *array, int n, int sum, int t) { if (t == n) { if (sum == 0) { count++; } return; } if (sum == 0) { // Find a solution count++; } else { if (sum >= array[t]) { // left tree find_combinations(array, n, sum - array[t], t + 1); } if (sum > 0) { // right tree find_combinations(array, n, sum, t + 1); } } } int main(void) { int a[] = {11, 3, 8, 4, 1, 7}; find_combinations(a, 6, 11, 0); printf("%d\n", count); system("pause"); return 0; }
==
本文转自zdd博客园博客，原文链接：http://www.cnblogs.com/graphics/archive/2009/06/03/1495466.html，如需转载请自行联系原作者
