DEV Community

Cover image for 40. Combination Sum II
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on

40. Combination Sum II

40. Combination Sum II

Difficulty: Medium

Topics: Array, Backtracking

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.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

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

Example 2:

  • Input: candidates = [2,5,2,1,2], target = 5
  • Output: [[1,2,2], [5]]

Constraints:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

Solution:

We can use a backtracking approach. The key idea is to sort the array first to handle duplicates easily and then explore all possible combinations using backtracking.

Let's implement this solution in PHP: 40. Combination Sum II

Explanation:

  1. Sorting: The candidates array is sorted to handle duplicates easily and to ensure combinations are formed in a sorted order.
  2. Backtracking: The backtrack function is used to explore all possible combinations.
    • If the target becomes zero, we add the current combination to the result.
    • We iterate over the candidates starting from the current index. If a candidate is the same as the previous one, we skip it to avoid duplicate combinations.
    • We subtract the current candidate from the target and recursively call the backtrack function with the new target and the next index.
    • The recursive call continues until we either find a valid combination or exhaust all possibilities.
  3. Pruning: If the candidate exceeds the target, we break out of the loop early since further candidates will also exceed the target.

This code will output all unique combinations that sum up to the target while ensuring that each candidate is used only once in each combination.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Image of Datadog

The Essential Toolkit for Front-end Developers

Take a user-centric approach to front-end monitoring that evolves alongside increasingly complex frameworks and single-page applications.

Get The Kit

Top comments (0)

Billboard image

Create up to 10 Postgres Databases on Neon's free plan.

If you're starting a new project, Neon has got your databases covered. No credit cards. No trials. No getting in your way.

Try Neon for Free →