Simple Backtracking Program with Explanation in Java

This guide will provide a detailed explanation of the Combination Sum problem, demonstrating how to solve it using backtracking in Java. This problem requires finding all unique combinations of numbers that sum up to a given target value, where the same number can be used multiple times.

Problem Statement

Given an array of distinct integers candidates and a target integer target, return all unique combinations of candidates where the chosen numbers sum to target. The same number may be chosen from candidates an unlimited number of times.

Example:

Input:

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

Output:

[[2, 2, 3], [7]]

Approach

We’ll use a backtracking approach to explore all possible combinations. The main steps are:

Initialize the Result List: Create a list to store all valid combinations.
Recursive Backtracking Function:
- Include the current candidate in the combination and recursively call the function with the reduced target.
- Exclude the current candidate and move to the next candidate.
- If the target becomes 0, add the current combination to the result.
Manage Combinations: Ensure that the combinations are unique and avoid redundant paths by carefully managing the list used to build combinations.

Java Code Implementation

Here’s a step-by-step Java implementation of the Combination Sum problem using backtracking:

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

public class CombinationSum {

    // Main function to find all unique combinations
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), candidates, target, 0);
        return result;
    }

    // Backtracking function
    private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] candidates, int remain, int start) {
        // If remaining target is less than 0, there is no valid combination
        if (remain < 0) return;
        // If remaining target is 0, we found a valid combination
        else if (remain == 0) result.add(new ArrayList<>(tempList));
        else {
            // Explore all candidates starting from 'start' index
            for (int i = start; i < candidates.length; i++) {
                tempList.add(candidates[i]); // Choose
                backtrack(result, tempList, candidates, remain - candidates[i], i); // Explore
                tempList.remove(tempList.size() - 1); // Un-choose (Backtrack)
            }
        }
    }

    public static void main(String[] args) {
        // Test example
        CombinationSum cs = new CombinationSum();
        int[] candidates = {2, 3, 6, 7};
        int target = 7;
        List<List<Integer>> results = cs.combinationSum(candidates, target);
        for (List<Integer> combination : results) {
            System.out.println(combination);
        }
    }
}

Detailed Explanation

Let’s break down the code and explain each part.

1. Main Method

public static void main(String[] args) {
    CombinationSum cs = new CombinationSum();
    int[] candidates = {2, 3, 6, 7};
    int target = 7;
    List<List<Integer>> results = cs.combinationSum(candidates, target);
    for (List<Integer> combination : results) {
        System.out.println(combination);
    }
}

Purpose: This method initializes the CombinationSum class, defines the input array candidates, and sets the target. It then calls the combinationSum method and prints each combination found.
Output: For the input [2, 3, 6, 7] and target 7, it prints the combinations [2, 2, 3] and [7].

2. CombinationSum Method

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(result, new ArrayList<>(), candidates, target, 0);
    return result;
}

Purpose: This method initializes the result list to store valid combinations. It then calls the backtrack function starting with an empty temporary list tempList and the initial target.
Parameters:
- candidates: Array of integers.
- target: The target sum to achieve.
Returns: A list of lists, where each list contains a combination of integers that sum up to target.

3. Backtrack Method

private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] candidates, int remain, int start) {
    if (remain < 0) return; // No valid combination
    else if (remain == 0) result.add(new ArrayList<>(tempList)); // Found a valid combination
    else {
        for (int i = start; i < candidates.length; i++) {
            tempList.add(candidates[i]); // Choose
            backtrack(result, tempList, candidates, remain - candidates[i], i); // Explore
            tempList.remove(tempList.size() - 1); // Un-choose (Backtrack)
        }
    }
}

Purpose: This recursive method explores all possible combinations by choosing candidates and reducing the remaining target.
Parameters:
- result: List to store all valid combinations.
- tempList: Temporary list to build the current combination.
- candidates: Array of integers.
- remain: Remaining target sum.
- start: Index to start from in the candidates array to avoid revisiting previous elements.
Steps:
- Base Cases:
  - If remain is less than 0, it means the current combination exceeds the target, so return without adding it to the result.
  - If remain equals 0, add the current combination to the result list.
- Exploration:
  - Iterate over the candidates starting from the index start to avoid duplicates.
  - Add the current candidate to the temporary list.
  - Recursively call backtrack with the reduced remain and the same start index to allow repeated use of the current candidate.
  - After the recursive call, remove the last element from tempList to explore other possibilities.

How Backtracking Works in This Problem

Initial Call: Start with an empty list and the full target value.
Recursive Exploration: Try adding each candidate to the current list and recursively check if the remaining target can be met with the same or other candidates.
Backtracking: If a candidate leads to a valid combination (i.e., the remaining target becomes 0), the combination is added to the result. If not, the candidate is removed, and the algorithm tries the next candidate.

Advantages

Systematic Search: Ensures all possible combinations are explored.
Simple Implementation: Conceptually straightforward and easy to implement.

Applications

Combinatorial Problems: Problems where you need to find combinations or subsets.
Constraint Satisfaction: Problems where a set of constraints needs to be met.

Conclusion

The backtracking approach efficiently handles the problem by exploring all potential combinations while avoiding unnecessary paths, making it a powerful technique for solving problems with constraints.

Feel free to try running this code with different inputs to see how it performs for various cases. If you have any questions or need further clarification, let me know in the comment section