leetcode 刷题 38 39

class Solution:
    def countAndSay(self, n: int) -> str:
        """
        :type n: int
        :rtype: str
        """
        if n<=1:
            return '1'
            
        pre_seq = self.countAndSay(n-1)
        count = 1
        ans = ''

        for i in range(len(pre_seq)):
            if i == len(pre_seq)-1 or pre_seq[i]!=pre_seq[i+1]:
                ans = ans + str(count) + pre_seq[i]
                count = 1
            else:
                count += 1
        
        return ans

class Solution:
    def combinationSum(self, candidates: 'List[int]', target: 'int') -> 'List[List[int]]':
        candidates.sort()
        return self.combinationSum_helper(candidates, 0, target)
    def combinationSum_helper(self, candidates, idx, target):
        if target == 0:
            return [[]]
        cur_res = []
        for i in range(idx, len(candidates)):
            if target < candidates[i]:
                break
            nxt_res = self.combinationSum_helper(candidates, i, target - candidates[i])
            if nxt_res != []:
                for s in nxt_res:
                    cur_res.append(s + [candidates[i]])
        return cur_res