Skip to main content

Leetcode 39: Combination Sum

 

1. Problem Statement (Simple Explanation):


You are given:

  • An array of distinct positive integers candidates.

  • A positive integer target.

You must find all unique combinations of numbers from candidates such that:

  • The sum of the chosen numbers equals target.

  • You can use the same number unlimited times.

  • Two combinations are considered different if the count of at least one number differs.

  • Return all combinations (order of combinations and order inside each combination does not matter).

The number of unique combinations is guaranteed to be < 150.


2. Examples:


Example 1:

Input: candidates = [2,3,6,7], target = 7

Valid combinations:

  • 2 + 2 + 3 = 7 → [2,2,3]

  • 7 = 7 → [7]

Output: [[2,2,3],[7]]


Example 2:

Input: candidates = [2,3,5], target = 8

Valid combinations:

  • 2 + 2 + 2 + 2 = 8 → [2,2,2,2]

  • 2 + 3 + 3 = 8 → [2,3,3]

  • 3 + 5 = 8 → [3,5]

Output: [[2,2,2,2],[2,3,3],[3,5]]


Example 3:

Input: candidates = [2], target = 1

No combination sums to 1.

Output: []


3. Approach – Backtracking (DFS) with Reuse Allowed:


This is a classic backtracking / DFS combination problem.


Intuition:


We explore combinations by:

  • Maintaining:

    • start index in candidates (to prevent permutation duplicates).

    • current list of chosen numbers.

    • remaining sum (initially target).

  • For each index i starting from start:

    • Option to include candidates[i]:

      • Add it to current.

      • Recurse with:

        • start = i (not i+1, because we can reuse the same number).

        • remaining = remaining - candidates[i].

    • Stop if remaining < 0 (over target).

    • If remaining == 0 → we found a valid combination; add a copy of current to the result.

We never go backwards in indices (we pass i as next start, not 0), which ensures combinations are generated in non-decreasing order of indices and no duplicates.


Algorithm (Step-by-Step):


  1. Optionally sort candidates (not required for correctness here, but can help pruning).

  2. Create an empty list result to collect valid combinations.

  3. Define backtrack(start, remaining, current):

    • If remaining == 0:

      • Add a copy of current to result; return.

    • If remaining < 0:

      • Return (invalid path).

    • For i from start to len(candidates)-1:

      • Let num = candidates[i].

      • Append num to current.

      • Call backtrack(i, remaining - num, current) (note i, not i+1, because unlimited uses).

      • Remove last element from current (backtrack).

  4. Call backtrack(0, target, []).

  5. Return result.


Pseudo-code:



Complexity:


Let:

  • n = len(candidates)

  • T = target

The worst-case time complexity is exponential in general (combinatorial number of solutions), but:

  • Input constraints (target ≤ 40, ≤ 150 combinations) keep it manageable.

  • Space: O(T) for recursion depth and current combination.


4. Java code:



5. C code:



6. C++ code:



7. Python code:



8. JavaScript code:



Comments

Post a Comment

Popular posts from this blog

Leetcode 1: Two Sum

  Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to  return the indices of two numbers in the array  such that: Conditions: Each input has  exactly one solution . You  cannot use the same element twice . You can return the answer in  any order . 2. Examples Example 1 Input:                                    nums = [2, 7, 11, 15], target = 9 Output:                                 [0, 1] Explanation:                     nums[0]+nums[1]=2+7=9              So we return [0, 1]. Example 2 Input:           ...
Post a Comment
Read more

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more