Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀
100DaysOfCode #CodingChallenge #ProblemSolving #DeveloperJourney
*Problem: *
https://www.geeksforgeeks.org/problems/combination-sum-iii--111703/1
Unique K-Number Sum
Difficulty: Medium
Given two integers n and k, the task is to find all valid combinations of k numbers that adds up to n based on the following conditions:
• Only numbers from the range [1, 9] used.
• Each number can only be used at most once.
Note: You can return the combinations in any order, the driver code will print them in sorted order.
Examples:
Input: n = 9, k = 3
Output: [[1, 2, 6], [1, 3, 5], [2, 3, 4]]
Explanation: There are three valid combinations of 3 numbers that sum to 9: [1 ,2, 6], [1, 3, 5] and [2, 3, 4].
Input: n = 3, k = 3
Output: []
Explanation: It is not possible to pick 3 distinct numbers from 1 to 9 that sum to 3, so no valid combinations exist.
Constraints:
1 ≤ n ≤ 50
1 ≤ k ≤ 9
Solution:
class Solution:
def combinationSum(self, n, k):
res = []
def backtrack(start, path, total):
if len(path) == k and total == n:
res.append(path)
return
if len(path) >= k or total > n:
return
for i in range(start, 10):
backtrack(i + 1, path + [i], total + i)
backtrack(1, [], 0)
return res
Top comments (0)