No.0016-CareerCup

Take an array and print non overlapping in order pairs. Example:
input => [1,2,3,4]
output: an array containing below elements
(1234)
(1)(234)
(1)(23)(4)
(1)(2)(34)
(12)(34)
(12)(3)(4)
(123)(4)
(1)(2)(3)(4)

1. 询问

如何应付空输入？假设返回空数组。
输入都是什么样的？假设输入就是这样的数字数组。要是说可能有字符的话，也无所谓，反正都要转换成为字符串处理。

2. 分析

直观做法

这题一看就和递归很有缘。
因此可以先尝试用递归来做。具体做法，就是每次遍历截取长度然后递归剩下的。当然中间结果需要保存起来，到最后存进总的结果里面。
简单来说，就是有s参数持有待处理字符串，假如是空，就直接将intermediate结果汇入最终结果，而intermediate也是一个参数，初始为空。然后对长度进行遍历，取一段加括号，放入intermediate里面，递归下一层。
这道题的迭代方法不是很直观，面试的时候不能强求。
至于时间复杂度分析，1个元素1种，2个元素2种，3个元素4种，4个元素8种，很明显n个元素是2^{(n-1)种。因此时间复杂度O(2}n)；递归深度最大为n，因为n个元素，因此空间复杂度为O（n）。

3. 代码

class Solution:
    def pairs(self, A):
        if not A:
            return []
        s = ''.join([str(x) for x in A])
        self.res = []
        self.recur(s, "")
        return self.res

    def recur(self, s, inte):
        if not s:
            self.res.append(inte)
            return
        for i in range(len(s)):
            self.recur(s[i+1:], inte + "(" + s[:i+1] + ")")

4. 总结

难度easy。