Leetcode backtracking problem

Posted on | Post modified

46. Permutations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def permutate(x):
    if len(x)==0:
        return []
    if len(x)==1:
        return [x]
    res=[]
    for i in range(len(x)):
        x[0],x[i]=x[i],x[0]

        temp=permutate(x[1:])

        for j in temp:

            res.append([x[0]]+j)
        x[0],x[i]=x[i],x[0]
    return res
a=[1,2,3]
permutate(a)
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]

46. Permutations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def permutate(x):
    if len(x)==0:
        return []
    if len(x)==1:
        return [x]
    res=[]
    visited=[]
    for i in range(len(x)):
        if x[i] in visited:
            continue
        else:
            visited.append(x[i])
            x[0],x[i]=x[i],x[0]

            temp=permutate(x[1:])

            for j in temp:

                res.append([x[0]]+j)
            x[0],x[i]=x[i],x[0]
    return res
a=[1,2,2]
permutate(a)
[[1, 2, 2], [2, 1, 2], [2, 2, 1]]

78. Subsets

Solution 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def subset(x):
    if len(x) == 0:
        return []
    if len(x) == 1:
        return [x]
    res = []
    head = [x[0]]
    tail = x[1:]
    res.append(head)
    for i in subset(tail):
        res.append(i)
        res.append(head + i)
    return res

print(subset([1,2,3]))

Solution 2:

1
2
3
4
5
6
7
8
9
10
11
def backtracking( nums, temp, res, start):
    res.append(list(temp))
    #print(res)
    for i in range(start,len(nums)):
        temp.append(nums[i])
        print(temp)
        backtracking(nums, temp, res, i+1)
        temp.pop()
    return res
a=[1,2,3]
backtracking(a,[],[],0)

[1]
[1, 2]
[1, 2, 3]
[1, 3]
[2]
[2, 3]
[3]





[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

90. Subsets II

Solution 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def subset(x):
    if len(x) == 0:
        return []
    if len(x) == 1:
        return [x]
    res = []
    head = [x[0]]
    tail = x[1:]
    res.append(head)
    for i in subset(tail):
        res.append(head + i)
        if i not in res:
            res.append(i)
    return res

print(subset([1,1]))

Solution 2:

1
2
3
4
5
6
7
8
9
10
11
12
def backtracking( nums, temp, res, start):
    if temp not in res:
        res.append(list(temp))
    #print(res)
    for i in range(start,len(nums)):
        temp.append(nums[i])
        print(temp)
        backtracking(nums, temp, res, i+1)
        temp.pop()
    return res
a=[1,2,2]
backtracking(sorted(a),[],[],0) # sorted is important

[1]
[1, 2]
[1, 2, 2]
[1, 2]
[2]
[2, 2]
[2]





[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

Solution 3:

1
2
3
4
5
6
7
8
9
10
11
12
def backtracking(nums, temp, res, start):
    res.append(list(temp))
    for i in range(start,len(nums)):
        if i > start and nums[i] == nums[i-1]:
            print(i)
            continue
        temp.append(nums[i])
        backtracking(nums, temp, res, i+1)
        temp.pop()
    return res
a=[1,2,1]
backtracking(a,[],[],0)
[[], [1], [1, 2], [1, 2, 1], [1, 1], [2], [2, 1], [1]]

39. Combination Sum

Solution 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def combination_sum(x, target):
    x = sorted(x)
    def helper(temp,x,target):
        if len(x) == 0 and len(temp) == 0:
            return []
        if len(x) == 0 and target != 0:
            return []

        if target ==0 and len(x) ==0 and len(temp) != 0:
            return [temp]

        res = []
        first = x[0]
        maxTime = target // first
        
        for i in range(0, maxTime + 1):
            newTarget = target - x[0] * i
            
          
            tmp = helper(temp + [first] * i, x[1:], newTarget)
            for j in tmp:
                res.append(j)
        return res
    return helper([], x, target)
print(combination_sum([1,2,3,4,5],6))

Solution 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def backtracking(x,target,temp,res,start):
    if sum(temp)==target:
        #print(type(temp))
        #print(list(temp))
        print(res)
        res.append(list(temp)) # here we must use list(temp)
        #print(res)
        #print(res)
    if sum(temp)>target:
        return
    if sum(temp)<target:
        for i in range(start,len(x)):
            temp.append(x[i])
            #print(temp)
            backtracking(x,target,temp,res,i)
            temp.pop()
    return res
a=[1,2,3]
backtracking(a,6,[],[],0)

[]
[[1, 1, 1, 1, 1, 1]]
[[1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 2]]
[[1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 2], [1, 1, 1, 3]]
[[1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 2], [1, 1, 1, 3], [1, 1, 2, 2]]
[[1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 2], [1, 1, 1, 3], [1, 1, 2, 2], [1, 2, 3]]
[[1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 2], [1, 1, 1, 3], [1, 1, 2, 2], [1, 2, 3], [2, 2, 2]]





[[1, 1, 1, 1, 1, 1],
 [1, 1, 1, 1, 2],
 [1, 1, 1, 3],
 [1, 1, 2, 2],
 [1, 2, 3],
 [2, 2, 2],
 [3, 3]]

1
2
3
4
5
6
7
8
9
10
11
def f(a,b):
    a.append(b)
    b.append(4)
    return a
print(f([],[3,4]))

def f(a,b):
    a.append(list(b))
    b.append(4)
    return a
print(f([],[3,4]))
[[3, 4, 4]]
[[3, 4]]

40. Combination Sum II

Solution 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
       
       newCandidate = []
       for i in candidates :
           if i <= target:
               newCandidate.append(i)

       def helper(forbidden,temp,x,target):
           if target < 0:
               return []
           if len(x) == 0 and len(temp) == 0:
               return []
           if len(x) == 0 and target != 0:
               return []

           if target ==0 and len(x) ==0 and len(temp) != 0:
               return [temp]


           first = x[0]
           if first in forbidden:
               return helper(forbidden, temp, x[1:], target)
           else:
               tmp1 = helper(forbidden + [first], temp, x[1:], target)
               tmp2 = helper(forbidden, temp + [first], x[1:], target - first)

           return tmp1 + tmp2
       return helper([],[], newCandidate, target)

Solution 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def backtracking(x,target,temp,res,start):
    if sum(temp)==target:
        #print(type(temp))
        #print(list(temp))
        print(res)
        res.append(list(temp)) # here we must use list(temp)
        #print(res)
        #print(res)
    if sum(temp)>target:
        return
    if sum(temp)<target:
        for i in range(start,len(x)):
            temp.append(x[i])
            #print(temp)
            backtracking(x,target,temp,res,i+1)
            temp.pop()
    return res
a=[1,2,3]
backtracking(a,6,[],[],0)

[]





[[1, 2, 3]]

216. Combination Sum III

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def backtracking(x,target,temp,res,start,k):
    if len(temp)==k and sum(temp)==target:     
        res.append(list(temp)) # here we must use list(temp)      
    elif sum(temp)<target and len(temp)<k:
        for i in range(start,len(x)):
            temp.append(x[i])
            #print(temp)
            backtracking(x,target,temp,res,i+1,k)
            temp.pop()
    else:
        return
    return res
a=[1,2,3,4,5,6,7,8,9]
backtracking(a,7,[],[],0,3)
[[1, 2, 4]]

22. Generate Parentheses

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def backtracking(x,temp,tempCount,res,n):
    if len(temp)==n*2 and tempCount['(']==tempCount[')']:
        res.append(''.join(list(temp)))
        #print(temp)
    elif tempCount['(']<tempCount[')'] or tempCount['(']>n:
        return
    else:
        for i in range(len(x)):
            temp.append(x[i])
            print(temp)
            tempCount[x[i]]+=1
            backtracking(x,temp,tempCount,res,n)
            temp.pop()
            tempCount[x[i]]-=1
    return res

backtracking(['(',')'],[],{'(':0,')':0},[],3)
['(']
['(', '(']
['(', '(', '(']
['(', '(', '(', '(']
['(', '(', '(', ')']
['(', '(', '(', ')', '(']
['(', '(', '(', ')', ')']
['(', '(', '(', ')', ')', '(']
['(', '(', '(', ')', ')', ')']
['(', '(', ')']
['(', '(', ')', '(']
['(', '(', ')', '(', '(']
['(', '(', ')', '(', ')']
['(', '(', ')', '(', ')', '(']
['(', '(', ')', '(', ')', ')']
['(', '(', ')', ')']
['(', '(', ')', ')', '(']
['(', '(', ')', ')', '(', '(']
['(', '(', ')', ')', '(', ')']
['(', '(', ')', ')', ')']
['(', ')']
['(', ')', '(']
['(', ')', '(', '(']
['(', ')', '(', '(', '(']
['(', ')', '(', '(', ')']
['(', ')', '(', '(', ')', '(']
['(', ')', '(', '(', ')', ')']
['(', ')', '(', ')']
['(', ')', '(', ')', '(']
['(', ')', '(', ')', '(', '(']
['(', ')', '(', ')', '(', ')']
['(', ')', '(', ')', ')']
['(', ')', ')']
[')']





['((()))', '(()())', '(())()', '()(())', '()()()']

320. Generalized Abbreviation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def backtracking(x,temp,res,n):
    if len(temp)==n:
        res.append(list(temp))
    else:
        for i in range(len(x)):
            temp.append(x[i])
            backtracking(x,temp,res,n)
            temp.pop()
    return res
backtracking([1,0],[],[],4)

def generalized_abbreviation(x):
    n=len(x)
    res=backtracking([1,0],[],[],n)
    newRes=[]
    for i in range(len(res)):
        index=res[i]
        temp=[]
        for j in range(n):
            if index[j]==1:
                temp.append(1)
            else:
                temp.append(x[j])
        newRes.append(temp)
    res=[]
    for i in range(len(newRes)):
        temp=newRes[i]
        stack=[]
        tmp={1:0}
        while temp:

            a=temp.pop(0)
            if a!=1:
                if tmp[1]!=0:
                    stack.append(str(tmp[1]))
                    tmp[1]=0
                stack.append(a)

            else:
                tmp[1]+=1
        if tmp[1]!=0:
            stack.append(str(tmp[1]))
        res.append(''.join(stack))
    return res
generalized_abbreviation("word")
['4',
 '3d',
 '2r1',
 '2rd',
 '1o2',
 '1o1d',
 '1or1',
 '1ord',
 'w3',
 'w2d',
 'w1r1',
 'w1rd',
 'wo2',
 'wo1d',
 'wor1',
 'word']

51. N queens

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def n_queen(n):
    if n == 1:
        return [["Q"]]
    if n == 2 or n == 3:
        return []

    def helper(x, n):
        if x == 0:
            return [[j] for j in range(n)]
        res = []
        for i in helper(x - 1, n):
            for j in range(n):
                flag = 1
                for k in range(len(i)):
                    # 1
                    if i[k] == j:
                        flag = 0
                        break

                    if x - k == abs(j - i[k]):
                        flag =0
                        break
                if flag == 1:
                    res.append(i + [j])
        return res
    def draw(a,n):
        res = []
        for x in a:
            s = ""
            for _ in range(x):
                s += "."
            s += "Q"
            for _ in range(n-x-1):
                s += "."
            res.append(s)
        return res



    res = helper(n - 1, n)
    for i in range(len(res)):
        res[i] = draw(res[i],n)
    return res


print(n_queen(2))