Day-2 Leetcode Coding Journey: Mastering Problem-Solving Techniques

Leetcode #39 Combination Sum

📌 Problem Statement

Given a set of distinct positive integers candidates and a target integer target, find all unique combinations in candidates where the chosen numbers sum to target.

Constraints:

• A number may be chosen multiple times in a combination.

• All numbers in candidates are distinct positive integers.

• The solution set must not contain duplicate combinations.

• The same number may be used unlimited times.

🚀 Code Implementation

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res=[]
        def func(start,path,total):
            if total==target:
                res.append(path[:])  
                return
            if total>target:
                return            
            for i in range(start,len(candidates)):
                path.append(candidates[i])
                func(i,path,total+candidates[i])  
                path.pop()  
        func(0,[],0)
        return res

Leetcode #40 Combination Sum II

📌 Problem Statement

Given a collection of candidates (which may contain duplicates) and a target integer target, find all unique combinations in candidates where the chosen numbers sum to target.

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

Constraints

• The input list may contain duplicates.

• Each number may be used at most once.

• The solution set must not contain duplicate combinations.

• The numbers in a combination do not need to be in a specific order.

🚀 Code Implementation

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []
        candidates.sort() 
        def func(start,path,total):
            if total==target:
                res.append(path[:])  
                return
            if total>target:
                return
            prev=-1  
            for i in range(start,len(candidates)):
                if candidates[i]==prev:  
                    continue  
                path.append(candidates[i])
                func(i+1,path,total+candidates[i]) 
                path.pop()  
                prev = candidates[i] 
        func(0,[],0)
        return res