algorithm - How to find all collection of numbers whose addition is same to the max number from list -

how find collection of numbers addition same max number list. example: input array={2,3,4,9} output = {2,3,4}{9}

it subset sum problem. check if subset exists particular sum.

here particular sum = max element

so first find max element of list , put equal sum

subset sum problem dynamic programming algorithm tells if there subset sum equals given number.

below example code explained , detailed here

#include <cstdio> #include <vector> using namespace std;  bool** dp;  void display(const vector<int>& v) {     (int = 0; < v.size(); ++i)         printf("%d ", v[i]);     printf("\n"); }  void output(const vector<int>& a, int i, int sum, vector<int>& p) {     if (i == 0 && sum != 0 && dp[0][sum]) {         p.push_back(a[i]);         display(p);         return;     }     if (i == 0 && sum == 0) {         display(p);         return;     }     if (dp[i - 1][sum]) {         vector<int> b = p;         output(a, - 1, sum, b);     }     if (sum >= a[i] && dp[i - 1][sum - a[i]]) {         p.push_back(a[i]);         output(a, - 1, sum - a[i], p);     } }  void find(const vector<int>& a, int sum) {     if (a.size() == 0 || sum < 0) return;     dp = new bool*[a.size()];     (int = 0; < a.size(); ++i) {         dp[i] = new bool[sum + 1];         dp[i][0] = true;     }     (int = 1; < sum + 1; ++i)         dp[0][i] = (a[0] == i) ? true : false;     (int = 1; < a.size(); ++i)         (int j = 0; j < sum + 1; ++j)             dp[i][j] = (a[i] <= j) ? dp[i - 1][j] || dp[i - 1][j - a[i]] : dp[i - 1][j];     if (!dp[a.size() - 1][sum]) {         printf("there no subsets sum %d\n", sum);         return;     }     vector<int> p;     output(a, a.size()-2, sum, p);  }  int main() {     vector<int> = {1,2,3,4,5,6,10};     int max = 10;     find(a, max);     return 0; } 

output

4 3 2 1  5 3 2  5 4 1  6 3 1  6 4 

so, have set , set have subset sum equals max_element of list. need start dynamic programming find subset after sorting list , hence input provided in above example sorted list.

actually exhaustive search results in o(2^n) time , hence need improve using dynamic programming , hence above method.