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(2n)；递归深度最大为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。
