find a sulution!

[wbgxx]

Enter two integers n and m, from the series 1,2,3 ....... n ，get a few numbers at random, it is equal to m, called for all possible combinations of them

[Kevin Drzycimski]

can you form a few seperated sentences? Or explain what you really want to do?

[wbgxx]

sorry! my English is very poor! "input two interger n and m, from the serious number 1, 2, 3....n, take out fews integers and make it is equal to m,list all possible combinations"

[Luc Pattyn]

He wants combinations! :)

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]

---

Prolific encyclopedia fixture proof-reader browser patron addict?
We all depend on the beast below.

---

[wbgxx]

Yeah,thanks

[theCPkid]

I feel what he wants is to input two numbers n and m and the program should choose some numbers from series 1,2..n whose sum equals m and return all such combinations. For n=10, m=8, the possible combinations are: 1+7 2+6 3+5 .. 1+1+6 1+2+5 .. .. there can be a lot of such combinations. This is probably the ideal candidate for DP? 1. store all possible ways to make 1 using numbers from given series and store them 2. likewise all possible ways to make 2. since 2 can only be either using it alone or 1+1 and then to make 1, you already have ways stored during step 1 and so on for oher nos. for 3 = 3, 2+1. use info. for ways to make 2 and you'll automatically get 3, 2+1, 1+1+1 for 4 = 4, 3+1...

[Radhakrishnan G]

Subset Sum problem I am pasting an algorithm, got this from a book

Algorithm SumOfSubSet(s,k,r)
// Find all subset of w[1:n] that sum to m. The values of x[j],
// 1 <j<k, have already been determined. s = w[1]*x[1] + ... + w[k-1]*x[k-1]
// and r = w[k] + .. + w[n]. The w[j] are in non decreasing order
// It is assumed that w[1]< m and sum of w[i] > m where i = 1..n
{
x[k] := 1;
if( s + w[k] = m ) then Write( x[1:k]); // Subset found
else if( s + w[k] + w[k+1] <= m )
then SumOfSub( s + w[k], k+1, r-w[k]);
if( (s+r-w[k] >= m) and (s + w[k+1] <= m )) then
{
x[k] := 0;
SumOfSub( s, k + 1, r - w[k]);
}
}

s = is the sum to be generated w is the set with size n, x is an array and if x[i] is one means ith element in w is in the subset k is the index of element in w we are examining r is the remaining sum that can be created from k +1th element to nth item in w

modified on Thursday, May 12, 2011 9:23 AM

[talazz]

Pleaze i need a help , i need an implementation for the subset sum problem using these algorithms 1. An exponential time exact algorithm 2. Fully polynomial-time approximation scheme