Combination Sum II - Practice Coding Problems

Combination Sum II - Problem

Array Backtracking Medium

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Important constraints:

Each number in candidates may only be used once in the combination
The solution set must not contain duplicate combinations

Return the answer as a list of lists, where each inner list represents a valid combination.

Input & Output

Example 1 — Basic Case with Duplicates

$ Input: candidates = [10,1,2,7,6,1,5], target = 8

› Output: [[1,1,6],[1,2,5],[1,7],[2,6]]

💡 Note: After sorting [1,1,2,5,6,7,10], we find combinations: 1+1+6=8, 1+2+5=8, 1+7=8, and 2+6=8. Each number is used at most once per combination.

Example 2 — Multiple Duplicates

$ Input: candidates = [2,5,2,1,2], target = 5

› Output: [[1,2,2],[5]]

💡 Note: After sorting [1,2,2,2,5], valid combinations are: 1+2+2=5 (using first two 2s) and 5=5. The combination [2,2,1] would be duplicate of [1,2,2].

Example 3 — No Valid Combinations

$ Input: candidates = [1,2], target = 4

› Output: []

💡 Note: No combination of [1,2] can sum to 4. Maximum possible sum is 1+2=3.

Constraints

1 ≤ candidates.length ≤ 100
1 ≤ candidates[i] ≤ 50
1 ≤ target ≤ 30

Visualization

Tap to expand

Understanding the Visualization

Input

Array [10,1,2,7,6,1,5] with target 8

Process

Sort array and use backtracking to find combinations

Output

All unique combinations: [[1,1,6],[1,2,5],[1,7],[2,6]]

Key Takeaway

🎯 Key Insight: Sort first to group duplicates, then skip duplicates at the same recursion level to avoid duplicate combinations

Asked in

a Amazon 45 M Microsoft 38 G Google 35 f Facebook 28

The key insight is to sort the array first, then use backtracking with duplicate skipping at the same recursion level. The optimal approach is backtracking with pruning. Time: O(2^n), Space: O(target)

Common Approaches

Approach	Time	Space	Notes
✓ Backtracking with Duplicate Handling	O(2^n)	O(target)	Use backtracking to build combinations while skipping duplicates at same recursion level
Brute Force - Generate All Subsets	O(2^n × n)	O(2^n × n)	Generate all possible subsets and filter those that sum to target

Backtracking with Duplicate Handling — Algorithm Steps

Sort candidates array to group duplicates
Use backtracking to try each candidate
Skip duplicates at same recursion level
Prune branches when sum exceeds target

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Array

Sort to group duplicates together: [1,1,2,5,6,7,10]

Build Combinations

Use backtracking to try each element, skip duplicates at same level

Prune Early

Stop when current sum exceeds target

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_COMBINATIONS 1000
#define MAX_COMBINATION_SIZE 20

int** globalResult;
int* globalReturnColumnSizes;
int globalReturnSize;

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

void backtrack(int* candidates, int candidatesSize, int target, int start, int* currentCombination, int currentSize) {
    if (target == 0) {
        globalResult[globalReturnSize] = (int*)malloc(currentSize * sizeof(int));
        for (int i = 0; i < currentSize; i++) {
            globalResult[globalReturnSize][i] = currentCombination[i];
        }
        globalReturnColumnSizes[globalReturnSize] = currentSize;
        globalReturnSize++;
        return;
    }
    
    if (target < 0) {
        return;
    }
    
    for (int i = start; i < candidatesSize; i++) {
        // Skip duplicates at same recursion level
        if (i > start && candidates[i] == candidates[i-1]) {
            continue;
        }
        
        // Early pruning
        if (candidates[i] > target) {
            break;
        }
        
        currentCombination[currentSize] = candidates[i];
        // Move to next index (i+1) since each number can only be used once
        backtrack(candidates, candidatesSize, target - candidates[i], i + 1, currentCombination, currentSize + 1);
    }
}

int** solution(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {
    qsort(candidates, candidatesSize, sizeof(int), compare); // Sort to handle duplicates
    
    globalResult = (int**)malloc(MAX_COMBINATIONS * sizeof(int*));
    globalReturnColumnSizes = (int*)malloc(MAX_COMBINATIONS * sizeof(int));
    globalReturnSize = 0;
    
    int currentCombination[MAX_COMBINATION_SIZE];
    backtrack(candidates, candidatesSize, target, 0, currentCombination, 0);
    
    *returnSize = globalReturnSize;
    *returnColumnSizes = globalReturnColumnSizes;
    return globalResult;
}

int main() {
    int candidates[20];
    int candidatesSize = 0;
    int target;
    
    // Simple parsing
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    char* token = strtok(line, "[,]");
    while (token != NULL && candidatesSize < 20) {
        candidates[candidatesSize++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    scanf("%d", &target);
    
    int returnSize;
    int* returnColumnSizes;
    int** result = solution(candidates, candidatesSize, target, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("[");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("%d", result[i][j]);
            if (j < returnColumnSizes[i] - 1) printf(",");
        }
        printf("]");
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

In worst case, explore all possible combinations, but pruning significantly reduces actual work

⚠ Quadratic Growth

Space Complexity

O(target)

Recursion depth limited by target value, plus space for current combination

✓ Linear Space

89.2K Views

High Frequency

~25 min Avg. Time

3.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Backtracking with Duplicate Handling — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler