Combination Sum in Java: Explanation & Practice

Problem summary

Given an array and target, find all unique combinations where the candidate numbers sum to target. Same number may be used unlimited times.

Starter code

public class Main {
    public static void main(String[] args) {
        int[] candidates = {2, 3, 6, 7};
        int target = 7;
        
        // Backtracking with reuse allowed
        // At each step: include current (stay at index) or skip (move to next)
        // Print all combinations
    }
}

Expected output and test cases

• candidates=[2,3,6,7], target=7

  [2,2,3]
  [7]

• candidates=[2,3,5], target=8

  [2,2,2,2]
  [2,3,3]
  [3,5]

• target=1, candidates=[2] → none

Hints

1. Sort candidates for easier pruning
2. For each candidate, try including it (stay at same index for reuse)
3. When sum > target, backtrack
4. When sum == target, add current combination to result

Related Data Structures & Algorithms exercises

• Practice Subsets (Power Set) in Java
• Practice Permutations in Java
• Practice N-Queens in Java

Practice all Data Structures & Algorithms exercises · Run this idea in the Java compiler