recursion.md

• Use yield

#-------------------------------------------------------------------------------
# Name:        Generate Parentheses
# Purpose:
#
#            Given n pairs of parentheses, write a function to
#            generate all combinations of well-formed parentheses.
#
#            For example, given n = 3, a solution set is:
#
#            "((()))", "(()())", "(())()", "()(())", "()()()"
#----------------------------------------------------------------------------
def generateParenthesis(n):
    return list(_generateParenthesis(n, n))

def _generateParenthesis(left, right):
    if left == 0 and right == 0:
        yield ""
    if left > 0:
        for x in _generateParenthesis(left - 1, right):
            yield x + ")"
    if left < right:
        for y in _generateParenthesis(left, right - 1):
            yield y + "("

• 取所有的元素。O(2^n)

#-------------------------------------------------------------------------------
# Name:        Subsets and Subsets II
# Purpose:
#
# Given a set of distinct integers, S, return all possible subsets.
#
# Note:
#
#    Elements in a subset must be in non-descending order.
#    The solution set must not contain duplicate subsets.
#
# For example,
# If S = [1,2,3], a solution is:
#        [
#          [3],
#          [1],
#          [2],
#          [1,2,3],
#          [1,3],
#          [2,3],
#          [1,2],
#          []
#        ]
#-------------------------------------------------------------------------------
def subsets(s):
    rst = [[]]
    s.sort()
    for e in s:
        rst += [x + [e] for x in rst]
    return rst

# The solution set must not contain duplicate subsets.
def subsetsWithDup(S):
    rst = [[]]
    S.sort()
    for e in S:
        rst += [x + [e] for x in rst if x + [e] not in rst]
    return rst

• Avoid memory error

#-------------------------------------------------------------------------------
# Name:        Pow(x, n)
# Purpose:
#       Implement pow(x, n).
#-------------------------------------------------------------------------------
def pow(x, n):
    if n == 0:
        return 1
    elif n == 1:
        return x
    elif n%2 == 1:
        y = pow(x, n/2)
        return y*y*x
    elif n%2 == 0:
        y = pow(x, n/2)
        return y*y
    elif n%2 == -1:
        y = pow(x, n/2)
        return y*y/x
    else:
        raise ValueError("n must be an integer")

• Combination sum I and II

class Solution:
    result = []
    def combinationSum2(self, candidates, target):
        self.combinationSumRecur(sorted(candidates), [], 0, target)
        return self.result

    def combinationSumRecur(self, candidates, current, start, target):
        if target == 0 and current not in self.result:
            self.result.append(current)
        else:
            while start < len(candidates) and candidates[start] <= target:
                self.combinationSumRecur(candidates, current + \
                    [candidates[start]], start + 1, target - candidates[start])
                start += 1

a = Solution()
print a.combinationSum2([10,1,2,7,6,1,5], 8)

class Solution:
    def combinationSum(self, candidates, target):
        result = []
        self.combinationSumRecur(sorted(candidates), result, [], 0, target)
        return result

    def combinationSumRecur(self, candidates, result, current, start, target):
        if target == 0:
            result.append(current)
        else:
            while start < len(candidates) and candidates[start] <= target:
                self.combinationSumRecur(candidates, result, current + \
                    [candidates[start]], start, target - candidates[start])
                start += 1

• Permutation I and II

def permute(nums):
    carry = [[]]
    for num in nums:
        nxt = []
        for element in carry:
            for i in range(len(element) + 1):
                nxt.append(element[:i] + [num] + element[i:])
        carry = nxt
    return carry

def permute2(nums):
    carry = [[]]
    for num in nums:
        nxt = []
        for element in carry:
            for i in range(len(element) + 1):
                new_element = element[:i] + [num] + element[i:]
                if new_element not in nxt:
                    nxt.append(new_element)
        carry = nxt
    return carry

print permute([1, 3, 3])
print permute2([1, 3, 3])