LeetCode 40: Combination Sum II Solution

Master LeetCode problem 40 (Combination Sum II), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

40. Combination Sum II

Medium

Array Backtracking

Problem Explanation

Explanation

To solve this problem, we can use backtracking along with sorting the candidate numbers to handle duplicates. The algorithm involves iterating through the candidate numbers and for each number, we either include it in the combination or skip it. We need to handle duplicates by skipping duplicate numbers to avoid duplicate combinations. We will maintain a current combination and update it as we explore different paths.

Algorithm

Sort the candidate numbers to handle duplicates.
Initialize an empty list to store the result combinations.
Define a backtracking function that takes the current combination, remaining target, start index, and candidate numbers as parameters.
In the backtracking function:
- If the remaining target is 0, add the current combination to the result list.
- Iterate through the candidate numbers starting from the current index:
  - If the current number is greater than the remaining target, break the loop.
  - If the current number is a duplicate, skip it.
  - Add the current number to the combination.
  - Recur with the updated combination, reduced target, and the next index.
  - Backtrack by removing the last added number from the combination.
Return the result list of combinations.

Time Complexity

The time complexity of this algorithm is O(2^N) where N is the number of candidates.

Space Complexity

The space complexity is O(N) where N is the number of candidates.

Solution Code

import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(result, new ArrayList<>(), candidates, target, 0);
        return result;
    }
    
    private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] candidates, int remain, int start) {
        if (remain == 0) {
            result.add(new ArrayList<>(tempList));
        } else {
            for (int i = start; i < candidates.length; i++) {
                if (i > start && candidates[i] == candidates[i - 1]) continue;
                if (candidates[i] > remain) break;
                tempList.add(candidates[i]);
                backtrack(result, tempList, candidates, remain - candidates[i], i + 1);
                tempList.remove(tempList.size() - 1);
            }
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 40 (Combination Sum II)?

This page provides optimized solutions for LeetCode problem 40 (Combination Sum II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 40 (Combination Sum II)?

The time complexity for LeetCode 40 (Combination Sum II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 40 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 40 in Java, C++, or Python.

Back to LeetCode Solutions