"""Leetcode 39. Combination Sum
Medium

URL: https://leetcode.com/problems/combination-sum/

Given a set of candidate numbers (candidates) (without duplicates) and a
target number (target), find all unique combinations in candidates where
the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:
- All numbers (including target) will be positive integers.
- The solution set must not contain duplicate combinations.

Example 1:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]
"""


class Solution(object):
    def _backtrack(self, result, temps, target, start, candidates):
        if target < 0:
            return None

        if target == 0:
            result.append(temps[:])
            return None

        for i in range(start, len(candidates)):
            if candidates[i] <= target:
                temps.append(candidates[i])
                self._backtrack(result, temps, target - candidates[i], i, candidates)
                temps.pop()

    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]

        Time complexity: O(n^k), where
          - n is the length of candidates,
          - k is target.
        Space complexity: O(k).
        """
        # Apply backtracking.
        result = []
        temps = []
        start = 0
        self._backtrack(result, temps, target, start, candidates)
        return result


def main():
    candidates = [2,3,6,7]
    target = 7
    print Solution().combinationSum(candidates, target)

    candidates = [2,3,5]
    target = 8
    print Solution().combinationSum(candidates, target)


if __name__ == '__main__':
    main()

@@ -703,16 +703,25 @@
 Solution
+Backtrack
 (object)
@@ -829,44 +829,166 @@
     
-return None%0A%0A        if target == 0:
+# No way to further combine numbers.%0A            return None%0A%0A        if target == 0:%0A            # Achieven combination sum so add %22copied%22 temps to results.
 %0A   
@@ -1254,32 +1254,73 @@
 , i, candidates)
+%0A%0A                # Pop for backtracking.
 %0A               
@@ -1490,16 +1490,45 @@
 %5Bint%5D%5D%0A%0A
+        Apply backtracking.%0A%0A
         
@@ -1674,38 +1674,8 @@
 %22%22%22%0A
-        # Apply backtracking.%0A
     
@@ -1829,16 +1829,44 @@
 main():%0A
+    # Output: %5B%5B7%5D,%5B2,2,3%5D%5D%0A
     cand
@@ -1909,32 +1909,41 @@
   print Solution
+Backtrack
 ().combinationSu
@@ -1965,16 +1965,56 @@
 arget)%0A%0A
+    # Output: %5B%5B2,2,2,2%5D,%5B2,3,3%5D,%5B3,5%5D%5D%0A
     cand
@@ -2063,16 +2063,25 @@
 Solution
+Backtrack
 ().combi

Revise class name and add comments