Find the two subsets with the same sum in an array

Question

I try to solve a coding question which requires me to give out the two subsets in an array with the same sum.

For example, our input could be [3,1,2,4]. My expected solution to this problem is [[3,2],[1,4]] or [[2,3],[4,1]](Either would be acceptable. But no duplicated answer accepeted, such as [[3,2],[1,4],[2,3],[4,1]]) because 1 + 4 = 2 + 3. And if my input cannot result in such a combination, my code can just output Null or [[]].

I tried to solve this problem using DFS (Depth First Search), and my current code looks like this:

public static List<List<Integer>> twoPartSum(int[] arr){

    // corner case

    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> part = new ArrayList<>();

    if(arr == null || arr.length <= 1){
        ret.add(part);
        return ret;
    }

    // usual case

    int sum = 0;
    for(int i : arr){
        sum += i;
    }

    helper(arr, 0, sum/2, 0, ret, part);

    return ret;

}

private static void helper(int[] arr, int curSum ,int target, int index, List<List<Integer>> ret, List<Integer> part){

    //base case
    if(curSum == target){

        ret.add(new ArrayList<>(part));
        return;
    }

    // such a pair does not exits
    if(curSum > target ){
        return;
    }


    for(int i = index; i < arr.length; i++){

        swap(arr, i, index);
        curSum += arr[index];
        part.add(arr[index]);

        helper(arr, curSum, target, index + 1, ret, part);

        curSum -= arr[index];
        part.remove(index);
        swap(arr, i, index);

    }


}

private static void swap(int[] arr, int i, int j){

    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;

}

My current result is [[3,2],[1,4],[2,3],[4,1]] with an input [3,1,2,4] Unfortunately, I cannot figure out how to deduplicate my result. Could anyone offer some idea? Thanks in advance!

There could be duplicate numbers in the input, like [3,1,1,1,2,4]. And, apparently, my current solution cannot cover this situation. I'll appreciate it if you can offer such a general algorithm as well. But if it is too difficult, I'll be happy to know the solution for a distinct array for now.

Answer 1

I finally figured out a better way to solve this problem. And I'd like to share with people who are interested in this question. The code can also deal with duplicate elements in the input array.

I changed the logic of this problem. The recursion tree for this code is shown as follows. Basically, it is a binary tree and each branch stands for whether add the element in the array or not. The index of the array is the depth of this tree.

                       /            \
  arr[0] = 3          3(add 3)       0(don't add 3)     depth(index of the arr) == 0  
                   /      \       /      \
  arr[1] = 1    1+3      0+3     1+0      0+0           depth == 1
               /  \     /   \   /   \    /   \
  arr[2] = 2 2+4  0+4  2+3 0+3 2+1  0+1 2+0  0+0        depth == 2
             /\   /\   /\  /\   /\   /\  /\   /\ 
            ......

The tree above is a complete solution for the sums of all subsets of the array. And, of course, we can stop any branch by specifying a stopping criterion for this specific problem, which is

// base case 1: found the answer
if(curSum == target){
    ret.add(new ArrayList<>(part));
    return;
}

An valid code to my problem is shown as follows:

public static List<List<Integer>> twoPartSum2(int[] arr){

    // corner case

    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> part = new ArrayList<>();

    if(arr == null || arr.length <= 1){
        ret.add(part);
        return ret;
    }

    // usual case

    Arrays.sort(arr); // make sure the same numbers will be lined together

    int sum = 0;
    for(int i : arr){
        sum += i;
    }

    helper2(arr, 0, sum/2, 0, ret, part);

    return ret;

}

private static void helper2(int[] arr, int curSum ,int target, int index, List<List<Integer>> ret, List<Integer> part){

    // base case 1: found the answer
    if(curSum == target){
        ret.add(new ArrayList<>(part));
        return;
    }

    // base case 2: solution not found
    if(index == arr.length || curSum > target){
        return;
    }

    // recursion case 1: adding current element in the candidate list ("part")
    part.add(arr[index]);
    helper2(arr, curSum + arr[index], target,index + 1,ret, part);
    part.remove(part.size()-1);

    // deduplicate the same elements
    while(index + 1 < arr.length && arr[index] == arr[index+1]){
        index++;
    }

    // recursion case 2: not adding current element in the candidate list ("part")
    helper2(arr, curSum, target, index + 1,ret,part);

}

Please note that, in order to deduplicate our solution, we must skip the same elements in our array, which is exactly why the array is sorted at the very beginning Arrays.sort(arr); And then we have the below to skip the same elements at each layer.

// deduplicate the same elements
while(index + 1 < arr.length && arr[index] == arr[index+1]){
    index++;
}

For example, if our array is [1,1,1,3]. Then we'll have a recursion tree shown as follows:

                           /             \
  arr[0] = 1              1               0
                     /        \           |    (the other two '1's are skipped)
  arr[1] = 1       1+1        0+1         |     
                  /   \        |          |     (the other one '1' is skipped)   
  arr[2] = 1    1+2   0+2      |          | 
               / \    / \     / \        / \
  arr[3] = 3 3+3 0+3 3+2 0+2 3+1 0+1   3+0 0+0

The answer is: 6, 3, 5, 2, 4, 1, 3, 0

Some of you may ask why do we have two 3? Well, in fact, they are different 3 in this problem since the first 3 is obtained by 1+1+1 and the second one is from 3, the last element in the array [1,1,1,3]. As a result, they are still different solutions to this problem.

The logic I used earlier in this question can still work but I prefer not to post it at this moment because it is more confusing. However, if anyone is still interested in this problem, please leave a comment and I'll update that when I am free. Thank you!

Answer 2

For de-duplicating your result, you can put an order on your subset, saying that the elements in each subset have to be in increasing order (or decreasing, if you prefer that). This means that [3,2] would be re-written into [2,3] and so you would retrieve [2,3],[2,3],[1,4],[1,4] in your example. If you store your subsets in a Set instead of an ArrayList, the duplicates will not be added in the first place, and you will have [2,3], [1,4].