Solution to Combination Sum III by LeetCode

15 Aug

Question Name: Combination Sum III

This is a typical recursionÂ problem. Find out the base case and recursive cases, and that’s the right solution.

7 Replies to “Solution to Combination Sum III by LeetCode”

1. micropentium6 says:

IMHO, that sounds too much. If we restrict the elements in the array in an increasing order, there is no need to track if a number in range [1, 9] has been used.

• micropentium6 says:

There is actually a bug in Leetcode testing code: given “1,100”, leetcode considers [[100]] as a valid answer, which breaks the rule that only number from [1, 9] can be considered for the combination…

• Sheng says:

Yes, you are right. Also because the result always has the fix length k. Thanks!

• micropentium6 says:

Hi Sheng,
You are kind. I was not completely right. Your code is fine. I should have read it thoroughly. list[bool] is not for tracking, it’s for storing. It saves the possible combination. That has been said, the extra recursion branch (with or without next_value, sounds like a DP approach) may not be necessary.
My 2cents!

• Sheng says:

Actually, my original plan is using the linked list in array candidate. I gave up because I am too lazy đź™‚

2. Here’s my solution. The feature is that it doesn’t make failed iterations.

• Actually, the condition below is not necessary:

Just,