Re: array of integers

Kemal Oral CANSIZLAR wrote:
>
> There is this question that is intriguing me. This is no homework
> or alike, I have just come across and would really like to have
> some hints on how to attack the problem.
>
> There is an array of integers, without any restriction. How can I
> come up with an algorithm to find all combinations of elements
> that add up to the numbers in the array. If array is {1, 3, 2, 5,
> 4}, result would be {1, 2} = 3 is in array; {1, 3} = 4 is in
> array; {2, 3} = 5 is in array; {1, 4} = 5 is in array.
>
> I look forward to any inputs, thank you,

The following solves a different problem, but illustrates a
backtracking algorithm. I think the technique applies directly to
your case.

/* find integral solutions to x*x + y*y + z*z ... = r*r */
/* Public domain, by C.B. Falconer, 2005-03-25 */

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

/* 181 allows operation with 16 bit ints */
#define MAXRADIUS 181
#define MAXDIMS 10
#define DEFDIMS 3

#if (INT_MAX / MAXRADIUS < MAXRADIUS)
# error "MAXRADIUS too big"
#endif

static unsigned int squares[MAXRADIUS+1];

struct soln {
int dims;
int radius;
long int id;
int sv[MAXDIMS+1]; /* solution vector */
};

/* -------------- */

static void help(void)
{
printf("Usage: diophan radius [dimensions]\n"
" with radius <= %d, dimensions in 1..%d\n%s\n",
MAXRADIUS, MAXDIMS,
"Solves equations of the form x1^2+x2^2...+xn^2 = r^2"
);
exit(0);
} /* help */

/* -------------- */

/* Fixed, courtesy of Peter Nilsson
% diophan 3 10
solve 3 10 (WAS)
1: 1 1 1 1 1 1 1 1 1 0 [7257600]
2: 1 1 1 1 1 2 0 0 0 0 [604800]
3: 1 2 2 0 0 0 0 0 0 0 [2880]
4: 3 0 0 0 0 0 0 0 0 0 [20]
[7865300]

The variations need to be a factored by 2 for each non-zero
dimension (+ or -). To calculate the combinations, you need
to group and count the number of similar ordinates.

For example, the variations for the solutions above should be...

1: 9x1 1x0 [10!/9!1! * 2^9]
2: 5x1 1x2 4x0 [10!/5!1!4! * 2^6]
3: 1x1 2x2 7x0 [10!/1!2!7! * 2^3]
4: 1x3 9x0 [10!/1!9! * 2^1]
*/

/* NULL input returns (and resets) accumulated sum */
static unsigned long int variations(struct soln *s)
{
unsigned long int vars;
static unsigned long int vartotal;
int d, dups;

vars = vartotal;
if (!s) vartotal = 0;
else {
/* How many variations of s are available by reflections */
/* useful test group for this are (rad, dims) =
9, 3; 25, 3; 45, 3; 10, 4; 3, 9; 3, 10; 8, 4 */
for (vars = dups = 1, d = s->dims; d; d--, dups++) {
if (s->sv[d]) vars *= 2;
vars *= d;
if (d != s->dims && (s->sv[d] != s->sv[d+1])) dups = 1;
/* dups has to be an integral factor here */
/* so the division will always be exact */
else vars /= dups;
}
vartotal += vars;
}
return vars;
} /* variations */

/* -------------- */

static void dumpsolution(struct soln *s)
{
int d;

if (s) { /* else just accumulated total vars */
s->id++;
printf("%5ld:", s->id);
for (d = 1; d <= s->dims; d++) {
printf(" %3d", s->sv[d]);
}
}
printf(" [%lu]\n", variations(s));
} /* dumpsolution */

/* -------------- */

/* brute force exhaustive search */
/* I have rediscovered the backtracking algorithm! :-) */
static void solve(int r, int dims)
{
int d; /* dimension index */
int needed[MAXDIMS+1]; /* solution criterion */
struct soln s; /* a solution develops here */

s.dims = dims; s.radius = r; s.id = 0;
for (d = 1; d <= dims; d++) s.sv[d] = 0;
needed[0] = squares[r];
s.sv[0] = 1; /* just to start the sequence */

for (d = 1; ; d++) {
for (s.sv[d] = s.sv[d-1]; s.sv[d] <= r; s.sv[d]++) {
needed[d] = needed[d-1] - squares[s.sv[d]];
if (needed[d] <= 0) { /* backtrack */
if (0 == needed[d]) dumpsolution(&s);
s.sv[d] = 0;
d--; /* use prev. dim */
if (d) continue;
return; /* all done */
}
else if (d < dims) break; /* check next dimension */
}
}
} /* solve */

/* -------------- */

int main(int argc, char **argv)
{
size_t temp;
char *errp;
unsigned int r, dims;

r = 0; dims = DEFDIMS;
if ((argc < 2) || (argc > 3)) help();
if (argc > 1) {
temp = strtoul(argv[1], &errp, 10);
if ((temp > MAXRADIUS) || (errp == argv[1])
|| (temp < 1)) help();
else r = temp;
}
if (argc > 2) {
temp = strtoul(argv[2], &errp, 10);
if ((temp > MAXDIMS) || (errp == argv[2])
|| (temp < 1)) help();
else dims = temp;
}
for (temp = 0; temp <= MAXRADIUS; temp++) {
squares[temp] = temp * temp;
}
printf("solve %d %d\n", r, dims);
solve(r, dims);
dumpsolution(NULL); /* the accumulated total */
return 0;
} /* diophan main */

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson


.

Relevant Pages