How to all possible ways in which any combination of n elements m times can be added to give a result

Question

This is kind of an extension to this question: Finding all possible combinations of numbers to reach a given sum

The difference is that in the above-linked question, each number(from the set of options) would be counted one time. But what if each number is allowed to be chosen multiple times? For example, if the given set of options is {1, 4, 9}, to get a total of 15, we can do any of the following:

a) 1*15
b) 4*3 + 1*2
c) 4*2 + 1*7
d) 4*1 + 1*11
e) 9*1 + 4*1 + 1*2
f) 9*1 + 1*6

As in the linked question, and based upon your examples, I assume you mean only *additions* of the numbers? — lurker, Jun 09 '18 at 16:39
Well, it's trivial to modify the code given in the link. Remove `remaining = numbers[i+1:]` and change `subset_sum(remaining, target, partial + [n]) ` to `subset_sum(numbers, target, partial + [n])`. You can do the work to change the redundant sequences like `1,1,1,1,1,1,1` to `1*7`. — lurker, Jun 09 '18 at 16:51
This looks like coin change problem to me. [Link](https://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/) — Pham Trung, Jun 09 '18 at 17:02

score 0 · Answer 1 · answered Jun 09 '18 at 19:35

Since you have asked all the possible combinations and not the best one so simple recursion can be used to obtain the results. The main idea is to:

1. Sort the array(non-decreasing).
2. First remove all the duplicates from array.
3. Then use recursion and backtracking to solve

A c++ solution for your problem:

#include <bits/stdc++.h>
using namespace std;

void getNumbers(vector<int>& ar, int sum, vector<vector<int> >& res,vector<int>& r, int i) {

    if (sum < 0)
        return;

    if (sum == 0)
    {
        res.push_back(r);
        return;
    }

    while (i < ar.size() && sum - ar[i] >= 0)
    {

       r.push_back(ar[i]); 


        getNumbers(ar, sum - ar[i], res, r, i);
        i++;
        r.pop_back();
    }
}

vector<vector<int> > getSum(vector<int>& ar, int sum)
{
    sort(ar.begin(), ar.end());

    ar.erase(unique(ar.begin(), ar.end()), ar.end());

    vector<int> r;
    vector<vector<int> > res;
    getNumbers(ar, sum, res, r, 0);

    return res;
}

int main()
{
    vector<int> ar;
    ar.push_back(1);
    ar.push_back(4);
    ar.push_back(9);

    int n = ar.size();

    int sum = 15; 
    vector<vector<int> > res = getSum(ar, sum);

    if (res.size() == 0)
    {
        cout << "Emptyn";
        return 0;
    }

    for (int i = 0; i < res.size(); i++)
    {
        if (res[i].size() > 0)
        {
            cout << " ( ";
            for (int j = 0; j < res[i].size(); j++)
                cout << res[i][j] << " ";
            cout << ")";
        }
    }
}

How to all possible ways in which any combination of n elements m times can be added to give a result

1 Answers1