algorithm - 生成不重复的子集组合？

Question

给定一个可能有重复数字的数字列表，返回所有可能的子集组合。

如果 S = [2,2,2]，一个解是:

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

--- 其实是一系列的问题，上面是Split String III---

拆分字符串

给一个字符串，你可以选择在一个字符或两个相邻的字符之后拆分字符串，使字符串只由一个字符或两个字符组成。输出所有可能的结果。

Example
Given the string "123"
return [["1","2","3"],["12","3"],["1","23"]]

拆分字符串 II

给一个字符串，你可以选择在一个字符或任意相邻的字符之后拆分字符串，使字符串由这些字符组成。输出所有可能的结果。

Example
Given the string "123"
return [['1', '2', '3'], ['1', '23'], ['12', '3'], ['123']]

拆分字符串三

给一个字符串，你可以选择在一个字符或任意相邻的字符之后拆分字符串，使字符串由这些字符组成。输出所有可能的结果。字符串可能包含重复数字，减少重复结果，按字典顺序排列。

Example
Given the string "222"
return [['2', '2', '2'], ['2', '22'], ['222']]

Answer 1

得到一个anser作为引用，使用split作为mark减少重复的dfs。

   def subsets4(self, S):
        res = []
        split = [False for _ in range(len(S))]
        split_num = {}
        self.count = 0 
        def dfs(start_index, tmp):
            self.count += 1 
            if start_index == len(S):
                res.append(tmp)
                return 
            for i in range(start_index,len(S)):
                if (i >=2 and S[i-1] == S[i] and split[i-2] == False and split_num[S[i]] != False):
                    continue
                split[i] = True
                if S[start_index] == S[i]:
                    split_num[S[i]] = True
                dfs(i + 1, tmp + [S[start_index:i+1]])
                split_num[S[i]] = False
                split[i] = False
        S.sort()
        dfs(0, [])
        print 'dfs count:', self.count,
        return res 

>>> subsets4([2, 2, 2, 2, 2])
>>> dfs count: 20 [[[2], [2], [2], [2], [2]], [[2], [2], [2], [2, 2]], [[2], [2], [2, 2, 2]], [[2], [2, 2], [2, 2]], [[2], [2, 2, 2, 2]], [[2, 2], [2, 2, 2]], [[2, 2, 2], [2, 2]], [[2, 2, 2, 2, 2]]]

--------------------附上拆分字符串答案----------------

Class Solution(object):


    def splitString(self, S):
        if s is None:
            return []

        res = []
        # dfs helper to search solution for index + 1, index + 2
        def dfs(start, tmp):
            if start == len(S):
                res.append(tmp)
            end = min(start + 2, len(S))
            for i in range(start, end):
                dfs(i+1, tmp + [S[start:i+1]])

        dfs(0, [])
        return res


    def splitString2(self, S):
        if s is None:
            return []

        res = []
        # dfs helper to search solution for index + 1, index + 2
        def dfs(start, tmp):
            if start == len(S):
                res.append(tmp)
            end = len(S)
            for i in range(start, end):
                dfs(i+1, tmp + [S[start:i+1]])

        dfs(0, [])
        return res

    def splitString3(self, S):
        res = []
        split = [False for _ in range(len(S))]
        split_num = {}

        def dfs(start, tmp):
            if start == len(S):
                res.append(tmp)
                return 
            for i in range(start,len(S)):
                if (i >=2 and S[i-1] == S[i] and split[i-2] == False and split_num[S[i]] != False):
                    continue
                split[i] = True
                if S[start] == S[i]:
                    split_num[S[i]] = True
                dfs(i + 1, tmp + [S[start:i+1]])
                split_num[S[i]] = False
                split[i] = False

        dfs(0, [])
        return res