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)