Finding All Combination Sum Up to a Target in Java

In this tutorial, we’ll explore a common problem in algorithm design: given an array of integers and a target sum, how can we find all possible combinations of numbers in the array that add up to the target? Furthermore, we’ll allow the repetition of numbers in our combinations, adding a twist to the classic combination sum problem.

Problem Statement

Given an array of integers, for example, {1, 2, 3, 4, 5, 6, 7}, and a target sum k = 4, our task is to find all unique combinations within the array that sum up to k. Importantly, we can use any integer in the array multiple times.

Expected OutPut: [[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2], [4]]

Approach

To tackle this problem, we employ a technique called backtracking, a form of recursion that explores all potential combinations and “backtracks” once it determines that a particular path won’t lead to a solution.

Step-by-Step Solution

1. Initialize: Start with an empty list to store combinations and another to store the current combination.
2. Choose: Iterate through the array, adding the current number to the ongoing combination.
3. Explore: Recursively try to find the next number that can contribute to the target sum, reducing the target by the current number’s value.
4. Unchoose: After exploring all possibilities with the current number, remove it from the ongoing combination to try the next number.
5. Goal: Once the sum of numbers in the current combination equals the target, add it to the list of valid combinations.

Java Implementation

import java.util.ArrayList;
import java.util.List;

public class CombinationSum {

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7};
        int k = 4;
        List<List<Integer>> combinations = findCombinations(array, k);
        System.out.println("Combinations that sum up to " + k + ": " + combinations);
    }

    private static List<List<Integer>> findCombinations(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, target, 0, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(int[] nums, int remain, int start, List<Integer> path, List<List<Integer>> result) {
        if (remain == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if (nums[i] > remain) continue;
            path.add(nums[i]);
            backtrack(nums, remain - nums[i], i, path, result);
            path.remove(path.size() - 1);
        }
    }
}

//OUTPUT
//[[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2], [4]]

Conclusion

Backtracking is a powerful technique for solving combination and permutation problems. It allows us to explore all possible solutions to a problem by building up candidates to the solutions incrementally. In this tutorial, we’ve applied backtracking to solve a variation of the combination sum problem, demonstrating its utility in finding all combinations that sum up to a given target.

Ref: https://leetcode.com/problems/combination-sum/description/

Happy coding!