Recursion

3 minute read

Problem (splitArray)

Given an array of ints, is it possible to divide the ints into two groups so that the sums of the two groups are the same? Every int must be in one group or the other. Implement a recursive helper and call it from splitArray().

Examples:

  • splitArray([2, 2]) → true
  • splitArray([2, 3]) → false
  • splitArray([5, 2, 3]) → true

Idea (short)

At each index you have two choices: put the current number in the left group or the right group. Recurse to the next index with updated sums. When you’ve placed all numbers (index == length), check if the two sums are equal. This is a classic backtracking / recursion pattern that explores a binary decision tree.

Java solution

public boolean splitArray(int[] nums) {
    return helper(nums, 0, 0, 0);
}

private boolean helper(int[] nums, int index, int leftSum, int rightSum) {
    // base case: all numbers considered
    if (index == nums.length) {
        return leftSum == rightSum;
    }
    int val = nums[index];
    // try putting current value in left group
    if (helper(nums, index + 1, leftSum + val, rightSum)) return true;
    // try putting current value in right group
    if (helper(nums, index + 1, leftSum, rightSum + val)) return true;
    // neither choice led to a solution
    return false;
}

Walkthrough: example [5, 2, 3]

We start at index 0 with leftSum = 0, rightSum = 0.

  1. Index 0 (value 5): choose left or right
    • Put 5 in left → leftSum=5, rightSum=0, index=1
    • Put 5 in right → leftSum=0, rightSum=5, index=1
  2. Continue with index 1 (value 2) for each branch, and so on.

One successful assignment is: put 5 in left, 2 in right, 3 in right → leftSum=5, rightSum=2+3=5 → equal ⇒ true.

Recursion tree (ASCII) for [5, 2, 3]

Each level represents a decision for an index; “L” = put in left, “R” = put in right.

                  start (index=0, L=0, R=0)
                 /                           \
    [L:5] (1, L=5, R=0)                [R:5] (1, L=0, R=5)
     /           \                        /            \  [L:5,L:2]   [L:5,R:2]          [R:5,L:2]     [R:5,R:2]  (2, L=7,R=0) (2, L=5,R=2)     (2,L=2,R=5)   (2,L=0,R=7)
/   \        /    \            ...           ... ... final leaves for index=3 (check equality)

Evaluate leaves (index==3):

  • Path L,L,L => sums L=10, R=0 → no
  • Path L,L,R => L=7, R=3 → no
  • Path L,R,L => L=8, R=2 → no
  • Path L,R,R => L=5, R=5 → yes (this is the successful path)
  • … other paths from starting R branch are checked similarly

Tips to visualize and practice

  • Draw the recursion tree on paper for small arrays (length ≤ 4). Label nodes with (index, leftSum, rightSum).
  • Trace a single successful path and then backtrack to see how alternatives are explored.
  • Exercises:
    • Try [1,1,1,1] (should be true)
    • Try [1,2,5] (should be false)
    • Modify the code to return one valid partition (lists of indices) instead of boolean.

Complexity

This recursive solution explores up to 2^n leaves (n = array length) in the worst case. For small inputs and learning purposes this is fine; for larger inputs use DP (subset-sum / partition problem) to reduce complexity.

// small test harness (optional)
public static void main(String[] args) {
    int[] a = {5,2,3};
    System.out.println(new YourClassName().splitArray(a)); // true
}

Classification & right category

Short answer: this problem is best taught as “recursive backtracking” (a depth-first search of the choice tree) but it also has a natural Dynamic Programming (DP) formulation.

  • Backtracking / Recursion: the straightforward solution explores binary choices for each element (put in left or right). This is great for teaching recursion and visualizing the recursion tree.
  • Dynamic Programming / Subset-sum: because the problem reduces to finding a subset with sum = total/2, you can solve it efficiently using DP (or bitset tricks). DP is preferable for larger inputs because it avoids exponential time.
  • DFS / Graph view (related problems): similar problems (like jump games) map cleanly to graph/DFS with a visited set.

Recommendation for your blog post:

  • Keep categories: [Algorithms] (don’t add extra categories — that may change the post URL since permalinks use categories).
  • Use tags for more granular classification: Recursion, Backtracking, Dynamic Programming, Partition, Visualization.

This keeps the permalink stable while making the post discoverable by topic.

You may also enjoy