CODEWITHSUNDEEP
javacalgorithm
c_prog_90
c_prog_90

Reputation: 949

Algorithm to find set of numbers of a given array with a condition

Given an integer array of size N by the user. Print all the possible sets such that sum of all possible numbers equate to a number in the array.

Example:

Array A[]= {1,2,3,4,5}

1+2=3..Output:1,2,3

1+3=4..Output:1,3,4

1+4=5..Output:1,4,5

Initial Design:

  1. Take a number and set it to SetSum
  2. Generate all sums excluding the selected number; checking that the formulated sum is same as the SetSum
  3. Print out the numbers that satisfies the conditions above.
  4. Iterate over the array and set the next number as SetSum

A much efficient Design/Implementation or different approach are welcome..

Upvotes: 2

Views: 1068

Answers (1)

Amal Antony
Amal Antony

Reputation: 6797

This problem requires you to find the subsets whose sum totals to a given number(here an element of the set). There are 2 approcahes to doing this:

  1. A brute force algorithm where you generate all the subsets manually and sum them all up which is of exponential order of growth (2^n combinations) or

  2. Use a dynamic programming approach to the problem and find the sum in polynomial time. This is a standard problem in algorithmics called the subset sum problem. If you are not familiar with the concept of dynamic programming, you can look up any algorithms text book. If you understand dynamic programming, then google for the subset sum problem. Hope that helps!

Upvotes: 2

Related Questions