algorithm to get subset of array with target sum is not giving working

Question

The problem is given an unsorted array, give subsets of array that can produce target sum:

For eg:

target =  15
data = {3,4,5,7,1,2,9};

Expected results (note the results are sorted for simplicity. not a requirement) :

[1, 2, 3, 4, 5]
[1, 2, 3, 9]
[1, 2, 5, 7]
[1, 3, 4, 7]
[1, 5, 9]
[2, 4, 9]
[3, 5, 7]

Here is my naive approach to this problem - simple and brute force.

public static void naiveSubset(int[] arr, int target){
        int sum=0;
        List<Integer> result = new ArrayList<>();
        for (int i=0; i< arr.length;i++){
                sum =arr[i];
                result.add(arr[i]);
         for (int j=0;j<arr.length;i++){
             if (sum==target){
                 System.out.println(result);
                 result.clear();
                 break;
             }
             else if (i!=j && sum+arr[j] <= target){
                 sum+=arr[j];
                 result.add(arr[j]);
               }
           }
         }
        }

For some reasons, I am not expecting the results. I tried browsing through the code to dig out any issues. But I could not find any. please algo experts, point me in correct direction!!

The results I get (for same input as above)

[3, 3, 3, 3, 3]
[9, 3, 3]

Answer 1

Your solution is wrong because it's a greedy approach. It decides if you should add a number or not based on the fact that adding it does not violate the sum, at the moment.

However, this greedy approach does not work, with a simple example of the following array: [1,9,6,5] and with sum=11.

Note that for any element you choose in the outer loop, next you will add 1 to the current set. But that will deny you the possibility to get the sum of 5+6.
Once you choose 5, you start adding number, starting with '1', and adding it. Once it is added - you will never get the correct solution.

Also note: Your double loop approach can generate at most O(n^2) different subsets, but there could be exponential number of subsets - so something must be wrong.

---

If you want to get all possible subsets that sum to the given sum, you can use a recursive solution.

At each step "guess" if the current element is in the set or not, and recurse for both options for the smaller problem - if the data is in the set, or if it's not.

Here is a simple java code that does it:

public static void getAllSubsets(int[] elements, int sum) {
    getAllSubsets(elements, 0, sum, new Stack<Integer>());
}
private static void getAllSubsets(int[] elements, int i, int sum, Stack<Integer> currentSol) { 
    //stop clauses:
    if (sum == 0 && i == elements.length) System.out.println(currentSol);
    //if elements must be positive, you can trim search here if sum became negative
    if (i == elements.length) return;
    //"guess" the current element in the list:
    currentSol.add(elements[i]);
    getAllSubsets(elements, i+1, sum-elements[i], currentSol);
    //"guess" the current element is not in the list:
    currentSol.pop();
    getAllSubsets(elements, i+1, sum, currentSol);
}

Note that if you are looking for all subsets, there could be exponential number of those - so an inefficient and exponential time solution is expected.

---

If you are looking for finding if such a set exist, or finding only one such set, this can be done much more efficiently using Dynamic Programming. This thread explains the logic of how it can be done.
Note that the problem is still NP-Hard, and the "efficient" solution is actually only pseudo-polynomial.

Answer 2

I think the major issue in your previous approach is that simply doing loops based upon the input array will not cover all the combinations of numbers matching the target value. For example, if your major loop is in ith, and after you iterate through the jth element in your secondary loop, your future combination based on what you have collected through ith element will never include jth one anymore. Intuitively speaking, this algorithm will collect all the visible combinations through numbers near each other, but not far away from each other.

I wrote a iterative approach to cope with this subset sum problem through C++ (sorry, not have a java environment at hand:P), the idea is basically the same as the recurrsive approach, which means you would record all the existing number combinations during each iteration in your loop. I have one vector<vector> intermediate used to record all the encountered combination whose value is smaller than target, and vector<vector> final used to record all the combinations whose sum is equal to target.

The detailed explanation is recorded inline:

/* sum the vector elements */
int sum_vec(vector<int> tmp){
    int sum = 0;
    for(int i = 0; i < tmp.size(); i++)
        sum += tmp[i];
    return sum;
}

static void naiveSubset(vector<int> arr, int target){
    /* sort the array from big to small, easier for us to
     * discard combinations bigger than target */
    sort(arr.begin(), arr.end(), greater<int>());

    int sum=0;
    vector<vector<int> > intermediate;
    vector<vector<int> > final;
    for (int i=0; i< arr.size();i++){
        int curr_intermediate_size = intermediate.size();
        for(int j = 0; j < curr_intermediate_size; j++){
            int tmpsum = sum_vec(intermediate[j]);
            /* For each selected array element, loop through all 
             * the combinations at hand which are smaller than target,
             * dup the combination, put it into either intermediate or 
             * final based on the sum */
            vector<int> new_comb(intermediate[j]);
            if(tmpsum + arr[i] <= target){
                new_comb.push_back(arr[i]);
                if(tmpsum + arr[i] == target)
                    final.push_back(new_comb);
                else
                    intermediate.push_back(new_comb);
            }
        }
        /* finally make the new selected element a separate entry
         * and based on its value, to insert it into either intermediate
         * or final */
        if(arr[i] <= target){
            vector<int> tmp;
            tmp.push_back(arr[i]);
            if(arr[i] == target)
                final.push_back(tmp);
            else
                intermediate.push_back(tmp);
        }
    }
    /* we could print the final here */
}

Just wrote it so please bear with me if there is any corner case that I did not consider well. Hope this helps:)