# if not append current char
# move index to the next char if the there are multiple repeated current chars
# so that we will not consider duplicated cases
idx = pos +1
while idx <len(action) and action[idx] == action[pos]:
idx += 1
# skip all duplicated char to move the next char
self.bt(sols, sol, action,idx, k)
Coding
class Solution(object):
def subSetsIIOfSizeK(self, set, k):
"""
input: string set, int k
return: string[]
"""
#
#idea: DFS
# each level in recursion tree = an action of char from action set. Then the next level should exclude that action
# then branch in one level = picking one action from the remaining action set
# sol: solution, sols: list of solutions, pos: position of the action, used to select action
# 1. check if solution length == k, if so add solution to result list
# 2. select one action from the remaining actions, that is, index >= pos and index <len(action)
# 3. add the action to the solution and use bt recursion to search action "after the position selected action"
# so that we will not pick the same solution again
# For example [a, b, c, d]
# after we pick b in the for loop, then we need to pick c, d, rather than a,c,d
# because when we pick b and then a, to get [b,a], it is as same as we pick a, then pick b to get [a,b]
#
# if we pick char before and after current char, then order matters. If we pick char only after current char,
# order not matter
#
#base case: k =0, return [""]
action = list(set)
action.sort()
sol = []
sols = []
self.bt(sols, sol, action,0, k)
return sols
def bt(self, sols, sol, action, pos, k):
if pos == len(action):
sols.append("".join(sol[:]))
return
# each char is considered once
# and append once
# we consider the duplicated char
sol.append(action[pos])
self.bt(sols, sol, action,pos+1, k)
sol.pop(-1)
# if not append current char
# move index to the next char if the there are multiple repeated current chars
# so that we will not consider duplicated cases
idx = pos +1
while idx <len(action) and action[idx] == action[pos]:
idx += 1
# skip all duplicated char to move the next char
self.bt(sols, sol, action,idx, k)