Blog Data Structure

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]]


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));
        for (int i = start; i < nums.length; i++) {
            if (nums[i] > remain) continue;
            backtrack(nums, remain - nums[i], i, path, result);
            path.remove(path.size() - 1);

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


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.


Happy coding!



About Author

As Neelabh Singh, I am a Senior Software Engineer with 6.6 years of experience, specializing in Java technologies, Microservices, AWS, Algorithms, and Data Structures. I am also a technology blogger and an active participant in several online coding communities.

You may also like

Blog Design Pattern

Understanding the Builder Design Pattern in Java | Creational Design Patterns | CodeTechSummit

Overview The Builder design pattern is a creational pattern used to construct a complex object step by step. It separates
Blog Tech Toolkit

Base64 Decode

Base64 encoding is a technique used to encode binary data into ASCII characters, making it easier to transmit data over