DevExCode

40. Combination Sum II

ArrayBacktracking

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

  1. Sort the candidate numbers to handle duplicates.
  2. Initialize an empty list to store the result combinations.
  3. Define a backtracking function that takes the current combination, remaining target, start index, and candidate numbers as parameters.
  4. 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.
  5. 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.

View Leetcode Problem
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);
            }
        }
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

  • Add import statement if required.
  • Optimize the code for better time or space complexity.
  • Add test cases to validate edge cases and common scenarios.
  • Handle error conditions or invalid inputs gracefully.
  • Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Previous QuestionNext Question