BackTracking_Fixed sum for array elements-白红宇

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
     
      #include
      
       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，如需转载请自行联系原作者