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. 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.

    • 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…

      • 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!

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

Leave a Reply

Your email address will not be published. Required fields are marked *

Please put your code into a <pre>YOUR CODE</pre> section. Thanks and Happy Coding!