Re: array of integers

Kemal Oral CANSIZLAR wrote:

Thanks for the clarification Willem. The paraphrase of yours is better; "all
subsets of the array that sum to an element of the array"
I am convinced the problem is NP-complete.
And inclusion of negative values make the problem even harder to tackle with
if you were to think of efficient ways.

I think I should impose a restriction on input, namely, allowing only
positive integers.


Allowing only positive values makes it easy:



#include <stdio.h>


#define COUNTOF(a) (sizeof(a)/sizeof(a)[0])
        /* These need to be in descending order */
int array[] = { 13,9, 8,6,5, 4,3 , 1};
int result[COUNTOF(array)] ;


int check(int val, int lev, int *arr, int cnt);
void doprint(int lev);


        /* check val can be constructed by adding (combinations of)
        ** element of arr[]
        ** result is put into result[lev]
        ** Note: this checks *any* combination, not just pairs.
        ** (The OP only mentioned pairs in his example)
        */
int check(int val, int lev, int *arr, int cnt)
{
int idx;
int diff;
int found=0;

         for(idx=0; idx < cnt; idx++) {
        diff = val - arr[idx] ;
        if (diff < 0) continue;
        result[lev] = arr[idx];
        if (diff == 0) {
                found++;
                doprint(lev);
                continue;
                }
#if PAIRS_ONLY
        if (lev >= 2) continue;
#endif
        found += check(diff, lev+1, arr+idx+1, cnt-idx-1);
        }
return found;
}


void doprint(int lev)
{
int idx;for (idx=0; idx <=lev; idx++) {
        fprintf(stdout, "%d%c" , result[idx]
        , (!idx)?'=': (idx<lev)?'+':'\n');
        }
}


int main()
{
int idx;
int debt;
int found=0;


for (idx=0; idx < COUNTOF(array); idx++) {
        debt = array[idx] ;
        result[0] = debt;
        found += check( debt, 1, array+idx+1, COUNTOF(array)-idx -1);
        }
fprintf(stdout, "Found=%d\n", found );
}

HTH,
AvK

( Hoping I am not doing your homework for you ... )
.

Relevant Pages

  • (patch for Bash) regex case statement
    ... Following up on my previous patch for regex conditional tests, ... /* Return an array of strings; ... int dollarflag, zeropad, compareflag; ... SHELL_VAR *var; ...
    (comp.unix.shell)
  • Re: Strategy or Iterator?
    ... It would be possible to write a class that returns the variations ... GNU General Public License for more details. ... protected CombinatoricOperator(Telements, int r) { ... An integer array backing up the original one to keep track of the ...
    (comp.lang.java.programmer)
  • (patch for Bash) regex conditional tests
    ... 'regex' are returned in array variable SUBMATCH. ... Skipping of positional parameters, array elements, string ... int dollarflag, zeropad, compareflag; ... SHELL_VAR *var; ...
    (comp.unix.shell)
  • Re: Warning on assigning a function-returning-a-pointer-to-arrays
    ... This declares pfunc as a function taking no arguments and returning ... int x, y; ... Presumably pfuncwill return a pointer to a single int, ... or the first of a sequence of "array 5 of int"s. ...
    (comp.lang.c)
  • Re: Memory Allocation Problem, please help
    ... typedef struct word_tag{ ... array is not an array. ... static int total_word_count; ... static int word_index(const char *word); ...
    (comp.lang.c)