Scribd
Upload
1 views

recursion

Uploaded by

krishkdd0
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
1 views

recursion

Uploaded by

krishkdd0
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

class Solution:

def letterCombinations(self, digits: str) -> list[str]:

res = []

digitToChar = {

"2": "abc",

"3": "def",

"4": "ghi",

"5": "jkl",

"6": "mno",

"7": "qprs",

"8": "tuv",

"9": "wxyz",

def backtrack(i, curStr):

if len(curStr) == len(digits):

res.append(curStr)

return

for c in digitToChar[digits[i]]:

backtrack(i + 1, curStr + c)

if digits:

backtrack(0, "")

return res

class Solution:

def combinationSum(self, nums: list[int], target: int) -> list[list[int]]:

res = []
nums.sort()

def dfs(i, cur, total):

if total == target:

res.append(cur.copy())

return

for j in range(i, len(nums)):

if total + nums[j] > target:

return

cur.append(nums[j])

dfs(j, cur, total + nums[j])

cur.pop()

dfs(0, [], 0)

return res

class Solution:

def partition(self, s: str) -> list[list[str]]:

res, part = [], []

def dfs(i):

if i >= len(s):

res.append(part.copy())

return

for j in range(i, len(s)):

if self.isPali(s, i, j):

part.append(s[i : j + 1])
dfs(j + 1)

part.pop()

dfs(0)

return res

def isPali(self, s, l, r):

while l < r:

if s[l] != s[r]:

return False

l, r = l + 1, r - 1

return True

class Solution:

def permute(self, nums: list[int]) -> list[list[int]]:

if len(nums) == 0:

return [[]]

perms = self.permute(nums[1:])

res = []

for p in perms:

for i in range(len(p) + 1):

p_copy = p.copy()

p_copy.insert(i, nums[0])

res.append(p_copy)

return res

class Solution:
def subsets(self, nums: list[int]) -> list[list[int]]:

res = []

subset = []

def create_subset(i):

if i == len(nums):

print(subset)

res.append(subset[:])

return

subset.append(nums[i])

create_subset(i+1)

subset.pop()

create_subset(i+1)

create_subset(0)

return res

nums = [1,2,3]

s=Solution()

res=s.subsets(nums)

print(nums)

You might also like