DEV Community

Dev Cookies
Dev Cookies

Posted on

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);
    }
}
Enter fullscreen mode Exit fullscreen mode

πŸ”Ή 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);
    }
}
Enter fullscreen mode Exit fullscreen mode

βœ… 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);
    }
}
Enter fullscreen mode Exit fullscreen mode

βœ… 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);
    }
}
Enter fullscreen mode Exit fullscreen mode

βœ… 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);
    }
}
Enter fullscreen mode Exit fullscreen mode

βœ… 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);
    }
}
Enter fullscreen mode Exit fullscreen mode

βœ… 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;
}
Enter fullscreen mode Exit fullscreen mode

πŸ”Ή 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).


Top comments (0)