πΉ 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 from1..9
that sum ton
. - 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).
Top comments (0)