Perfect Sum Problem with repetitions allowed

Question

Given an array of integers and a sum, the task is to print all subsets of given array with sum equal to given sum with repetitions allowed.

Examples :

Input : arr = {1, 5, 6}, N = 7

Output :
1 1 1 1 1 1 1
1 1 5
1 5 1
5 1 1
1 6
6 1

I have already gone through related DP questions from https://www.geeksforgeeks.org/perfect-sum-problem-print-subsets-given-sum/ , https://www.geeksforgeeks.org/ways-sum-n-using-array-elements-repetition-allowed/ and find all subsets that sum to a particular value

I haven't found a way or any clues on how to solve this question with repetitions allowed. Any leads would be helpful.

Finding the count is a DP problem while finding all valid patterns will become a backtracking problem as answered by libik. — รยקคгรђשค, Dec 18 '18 at 09:01

גלעד ברקן · Accepted Answer · 2018-12-25T16:34:29.520

4

Something like this?

function f(A, N, r=[], s=N){
  if (s == 0)
    return [r];

  result = [];

  for (let a of A)
    if (a <= s)
      result = result.concat(
        f(A, N, r.slice().concat(a), s-a));

  return result;
}

console.log(JSON.stringify(f([1,5,6], 7)));

edited Dec 25 '18 at 16:34

answered Dec 18 '18 at 17:59

גלעד ברקן

23,602
3
25
61

2

Would be much more helpful if you use readable variable names and brackets – Sudhir N Jul 18 '19 at 04:20
1

@SudhirN oh, sorry - `s`: current sum; `N`: target sum; `a`: element of `A`; `A`: given array; `r`: result. Not sure what you mean by helpful brackets. – גלעד ברקן Jul 18 '19 at 09:58

score 1 · Answer 2 · edited Dec 24 '19 at 08:15

Here is a simple solution in Java:

public class PrintAllSubsets {

    public static void main(String[] args) {
        int arr []= {1, 5, 6}; 
        int N = 7;
        allSubsets(arr,N,"");
    }

    private static void allSubsets(int[] arr, int n, String res) {

        if(n == 0) {
            System.out.println(res);
            return;
        }
        for(int i = 0; i<arr.length;i++) {
            if(n >= arr[i]) {
                allSubsets(arr, n-arr[i], res + arr[i]);
            }
        }
    }

}

score 0 · Answer 3 · answered Dec 17 '18 at 16:57

Sort the input array (if you can) and then use https://en.wikipedia.org/wiki/Backtracking to get all possible solutions. Just go from the lowests number and if it cannot fit, just start returning and check if number one-item higher (in input array) can fit instead.

Perfect Sum Problem with repetitions allowed

3 Answers3

Linked