dfs.py

class Solution:
    def combinationSum(self, candidates, target):
        self.res = []
        self.dfs(sorted(candidates), [], target)
        return self.result
        
    def dfs(self, candidates, current, target):
        if target == 0:
            self.res.append(current)
            return
        for i, x in enumerate(candidates):
            if target < x:
                continue
            self.dfs(candidates[i:], current + [x], target - x)
            
class Solution:
    # @param num, a list of integer
    # @return a list of lists of integers
    def permute(self, num):
        self.res = []
        self._permute(num, [])
        return self.res
        
    def dfs(self, num, current):
        if len(num) == 0:
            self.res.append(current)
            return
        for i in xrange(len(current) + 1):
            self.dfs(num[1:], current[:i] + [num[0]] + current[i:])  

class Solution:
    # @return a list of lists of integers
    def combine(self, n, k):
        self.res = []
        self.N = n
        self.K = k
        self.dfs(1, [])
        return self.res

    def dfs(self, i, current):
        if len(current) == k:
            self.res.append(current)
            return
        for j in range(i, self.N + 1):
            self.dfs(j + 1, current + [j])
            
            
class Solution:
    def subsets(self, s):
        s.sort()
        self.res = []
        self._subsets(s, [])
        return self.res
        
    def _subsets(self, s, current):
        if not s:
            self.res.append(current)
            return
        first, s = s[0], s[1:]
        self._subsets(s, current)
        self._subsets(s, current + [first])
        
class Solution:
    # @param s, a string
    # @return a list of lists of string
    def partition(self, s):
        self.result = []
        self.N = len(s)
        self.dfs(s, [], 0)
        return self.result
        
    def dfs(self, s, current, i):
        if i == self.N:
            self.result += [current]
            return 
        for j in range(i, self.N):
            if self.isPalindrome(s[i: j + 1]):
                self.dfs(s, current + [s[i: j + 1]], j + 1)
                
    def isPalindrome(self, s):
        for i in range(len(s) / 2):
            if s[i] != s[-i-1]:
                return False
        return True