DEV Community

DevCorner
DevCorner

Posted on

Generating Unique Subsets and Finding Subset Sums in Java

When working with arrays, one common problem is generating all possible subsets. However, if the array contains duplicate elements, handling uniqueness becomes a challenge. In this blog, we will explore how to generate unique subsets of an array, find subsets whose sum matches a given target, and also find unique combinations that sum to a target value.

1. Generating Unique Subsets

Approach:

  • Sorting the Array: This ensures that duplicate numbers are adjacent, making it easier to skip them.
  • Backtracking: We recursively explore all subsets.
  • Skipping Duplicates: If a number is the same as the previous one (except for the first occurrence in a new recursion level), we skip it.

Java Implementation: 

import java.util.*;

public class UniqueSubsets {
    public static List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums); // Sort to handle duplicates
        backtrack(result, new ArrayList<>(), nums, 0);
        return result;
    }

    private static void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums, int start) {
        result.add(new ArrayList<>(tempList));
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) continue; // Skip duplicates
            tempList.add(nums[i]);
            backtrack(result, tempList, nums, i + 1);
            tempList.remove(tempList.size() - 1);
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

Example Output: 

Input: [1, 2, 2]
Output: [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
Enter fullscreen mode Exit fullscreen mode

2. Finding Subsets with a Given Sum

Approach:

  • Sorting the Array: Helps in handling duplicates.
  • Backtracking: Finds subsets whose sum matches the target.
  • Skipping Duplicates: Ensures unique subsets.
  • Pruning: Stops recursion if the sum exceeds the target.

Java Implementation: 

public static List<List<Integer>> subsetSum(int[] nums, int target) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums); // Sort to handle duplicates
    backtrackSum(result, new ArrayList<>(), nums, target, 0, 0);
    return result;
}

private static void backtrackSum(List<List<Integer>> result, List<Integer> tempList, int[] nums, int target, int sum, int start) {
    if (sum == target) {
        result.add(new ArrayList<>(tempList));
        return;
    }
    for (int i = start; i < nums.length; i++) {
        if (i > start && nums[i] == nums[i - 1]) continue; // Skip duplicates
        if (sum + nums[i] > target) break; // Prune the recursion
        tempList.add(nums[i]);
        backtrackSum(result, tempList, nums, target, sum + nums[i], i + 1);
        tempList.remove(tempList.size() - 1);
    }
}
Enter fullscreen mode Exit fullscreen mode

Example Output: 

Input: [1, 2, 2, 3, 5], Target Sum = 5
Output: [[2, 3], [5]]
Enter fullscreen mode Exit fullscreen mode

3. Finding Unique Combination Sums

Approach:

  • Sorting the Array: Helps in skipping duplicates.
  • Backtracking: Iterates over numbers and selects valid ones.
  • No Reuse of Elements: Unlike subset sum, each number can be chosen only once per combination.

Java Implementation: 

public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(candidates);
    backtrackCombination(result, new ArrayList<>(), candidates, target, 0);
    return result;
}

private static void backtrackCombination(List<List<Integer>> result, List<Integer> tempList, int[] candidates, int target, int start) {
    if (target == 0) {
        result.add(new ArrayList<>(tempList));
        return;
    }
    for (int i = start; i < candidates.length; i++) {
        if (i > start && candidates[i] == candidates[i - 1]) continue; // Skip duplicates
        if (candidates[i] > target) break;
        tempList.add(candidates[i]);
        backtrackCombination(result, tempList, candidates, target - candidates[i], i + 1);
        tempList.remove(tempList.size() - 1);
    }
}
Enter fullscreen mode Exit fullscreen mode

Example Output: 

Input: [10, 1, 2, 7, 6, 1, 5], Target Sum = 8
Output: [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
Enter fullscreen mode Exit fullscreen mode

Conclusion

By using backtracking and sorting, we can efficiently generate unique subsets, find subset sums, and compute unique combination sums. These approaches are useful in coding interviews and competitive programming. Let me know if you have any questions or improvements! 🚀

Top comments (0)