I start Leetcode for a week, I am really dead...
the first week, I am working on TOP 100 liked, specifically:

  • backtrack
  • binary tree
  • link list
  • array

Backtrack

The main idea here is :

    res = []
    def backtrack(path):
        if exit condition:
            res.append(path)
            return

        # choose the next element on the path
        if add this element:
            path.append(this element)
            backtrack(path)
            path.pop() # if you back to current step, we cannot change the path in current world

    backtrack([])
    return res

Subsets

problem 78 & 90

for unique set ([1,2,3]), every element can only be used once, we need to have a begin to get rid of repeated elements
for a non-unique set ([1,2,2]), sort first in order to skip the repeated elements, also need a begin. The selection part is if if i > start and nums[i] == nums[i-1]: continue

Combination

problem 77 & 39 & 40

For combination questions, [1,2] and [2,1] is the same, so we only consider the rest of unchosen elements, like in problem 77:

for i in range(begin, n+1):
    path.append(i)
    backtrack(i+1, path)
    path.pop()

when we are dealing with the non-unique set, to get rid of go into the same world multiple times, we need to have a condition like:

if i > begin and candidates[i] == candidates[i-1]:
    continue

think about the code above, when we look some repeat number (start a same world we have already started) after the begin, we need to skip.

Permutation

Problem 46 & 47

sequence in-sensitive, so in this case, when we deal with a non-unique set, we need to use used and sort. if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue.

so why not used[i-1]

when used[i-1], it is used, so in that case, we can select the next same number. When used[i-1] == False, the last level backtracked, if we select the next same number, we are using it as the first member and try to start a repeated world!

Parition

Problem 131 & 93

Search

Problem 51 & 37 & 79