Dev Cookies

Posted on Sep 1

Blog 4: Combination & Combinatorial Search (Extended Guide)

🔹 Introduction

The combination pattern focuses on choosing elements (without regard to order). Unlike permutations (order matters), here we only care about unique groups.

This pattern appears in problems like:

k-combinations (choose k out of n).
Combination Sum family of problems (LeetCode 39, 40, 216, 377).
Letter case permutations.
Palindrome partitioning.

👉 Interviewers love combinations because it tests recursion + pruning + constraints.

🔹 Core Template

void backtrack(int start, List<Integer> current, int[] nums, List<List<Integer>> results) {
    // Add to results if valid
    results.add(new ArrayList<>(current));

    for (int i = start; i < nums.length; i++) {
        // Choose
        current.add(nums[i]);

        // Explore (move forward)
        backtrack(i + 1, current, nums, results);

        // Undo
        current.remove(current.size() - 1);
    }
}

🔹 Variations of Combination Problems

Let’s cover all major ones with code snippets.

✅ 1. k-Combinations (Choose k out of n)

Input: n=4, k=2
Output: [ [1,2], [1,3], [1,4], [2,3], [2,4], [3,4] ]

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> results = new ArrayList<>();
    backtrack(1, new ArrayList<>(), n, k, results);
    return results;
}

private void backtrack(int start, List<Integer> current, int n, int k, List<List<Integer>> results) {
    if (current.size() == k) {
        results.add(new ArrayList<>(current));
        return;
    }

    for (int i = start; i <= n; i++) {
        current.add(i);
        backtrack(i + 1, current, n, k, results);
        current.remove(current.size() - 1);
    }
}

✅ 2. Combination Sum I (LeetCode 39)

Input: candidates=[2,3,6,7], target=7
Output: [ [2,2,3], [7] ]
Trick: You can reuse the same number multiple times.

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

private void backtrack(int start, List<Integer> current, int[] candidates, int target, List<List<Integer>> results) {
    if (target == 0) {
        results.add(new ArrayList<>(current));
        return;
    }
    if (target < 0) return;

    for (int i = start; i < candidates.length; i++) {
        current.add(candidates[i]);
        backtrack(i, current, candidates, target - candidates[i], results); // reuse allowed
        current.remove(current.size() - 1);
    }
}

✅ 3. Combination Sum II (LeetCode 40)

Input: candidates=[10,1,2,7,6,1,5], target=8
Output: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
Trick: Each number can only be used once & must handle duplicates.

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    Arrays.sort(candidates);
    List<List<Integer>> results = new ArrayList<>();
    backtrack(0, new ArrayList<>(), candidates, target, results);
    return results;
}

private void backtrack(int start, List<Integer> current, int[] candidates, int target, List<List<Integer>> results) {
    if (target == 0) {
        results.add(new ArrayList<>(current));
        return;
    }

    for (int i = start; i < candidates.length; i++) {
        if (i > start && candidates[i] == candidates[i - 1]) continue; // skip duplicate
        if (candidates[i] > target) break;

        current.add(candidates[i]);
        backtrack(i + 1, current, candidates, target - candidates[i], results); // i+1 since single use
        current.remove(current.size() - 1);
    }
}

✅ 4. Combination Sum III (LeetCode 216)

Find k numbers from 1..9 that sum to n.
Input: k=3, n=7
Output: [ [1,2,4] ]

public List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> results = new ArrayList<>();
    backtrack(1, new ArrayList<>(), k, n, results);
    return results;
}

private void backtrack(int start, List<Integer> current, int k, int target, List<List<Integer>> results) {
    if (target == 0 && current.size() == k) {
        results.add(new ArrayList<>(current));
        return;
    }

    for (int i = start; i <= 9; i++) {
        if (i > target) break;

        current.add(i);
        backtrack(i + 1, current, k, target - i, results);
        current.remove(current.size() - 1);
    }
}

✅ 5. Combination Sum IV (LeetCode 377 – DP)

⚡ Twist: Count combinations, not list them (Dynamic Programming).

✅ 6. Letter Case Permutations (LeetCode 784)

Input: "a1b2"
Output: "a1b2", "a1B2", "A1b2", "A1B2"

public List<String> letterCasePermutation(String s) {
    List<String> results = new ArrayList<>();
    backtrack(0, new StringBuilder(), s.toCharArray(), results);
    return results;
}

private void backtrack(int index, StringBuilder current, char[] chars, List<String> results) {
    if (index == chars.length) {
        results.add(current.toString());
        return;
    }

    char c = chars[index];
    if (Character.isLetter(c)) {
        current.append(Character.toLowerCase(c));
        backtrack(index + 1, current, chars, results);
        current.deleteCharAt(current.length() - 1);

        current.append(Character.toUpperCase(c));
        backtrack(index + 1, current, chars, results);
        current.deleteCharAt(current.length() - 1);
    } else {
        current.append(c);
        backtrack(index + 1, current, chars, results);
        current.deleteCharAt(current.length() - 1);
    }
}

✅ 7. Palindrome Partitioning (LeetCode 131)

Input: "aab"
Output: [ ["a","a","b"], ["aa","b"] ]

public List<List<String>> partition(String s) {
    List<List<String>> results = new ArrayList<>();
    backtrack(0, new ArrayList<>(), s, results);
    return results;
}

private void backtrack(int start, List<String> current, String s, List<List<String>> results) {
    if (start == s.length()) {
        results.add(new ArrayList<>(current));
        return;
    }

    for (int end = start + 1; end <= s.length(); end++) {
        String sub = s.substring(start, end);
        if (isPalindrome(sub)) {
            current.add(sub);
            backtrack(end, current, s, results);
            current.remove(current.size() - 1);
        }
    }
}

private boolean isPalindrome(String s) {
    int l = 0, r = s.length() - 1;
    while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
    return true;
}

🔹 Complexity Analysis

Subset/Combination generation: O(2^n)
Combination Sum: exponential but pruned with constraints.
Palindrome partitioning: O(2^n * n)

🔹 Interview References

LeetCode 39, 40, 216, 377
LeetCode 784 (Letter Case Permutation)
LeetCode 131 (Palindrome Partitioning)
Asked in Google, Microsoft, Amazon, Adobe, Facebook

🔹 Key Takeaways

✅ Combinations = choose elements (order doesn’t matter).
✅ Use start index to avoid duplicates & enforce forward-only choice.
✅ Palindrome + Letter Case = specialized variations.
✅ Combination Sum family = top FAANG interview favorites.

🔹 What’s Next?

In Blog 5: Constraint Satisfaction Pattern, we’ll explore Sudoku Solver, N-Queens revisited, Word Search, and CSP techniques (constraint pruning, branch & bound).

DEV Community