字符串的组合

• 题源：《剑指 Offer: 面试题 38》P110
• 在线：LeetCode: 46

题目

输入三个字符 a、b、c，则它们的组合有 a、b、c、ab、ac、 bc、abc。当交换字符串中的两个字符时，虽然能得到两个不同的排列，但却是同一个组合。比如 ab 和 ba 是不同的排列，但只算一个组合。

思路

如果输入 n 个字符，则这 n 个字符能构成长度为 1,2,...,n 的组合。在求 n 个字符的长度为 m (1≤m≤n)的组合的时候，我们把这 n 个字符分成两部分:第一个字符和其余的所有字符。如果组合里包含第一个字符，则下一步在剩余的字符里选取 m-1 个字符;如果组合里不包含第-一个字符，则下一步在剩余的 n-l 个字符里选取 m 个字符。也就是说，我们可以把求 n 个字符组成长度为 m 的组合的问题分解成两个子问题，分别求 n-1 个字符中长度为 m-1 的组合，以及求 n-1 个字符中长度为 m 的组合。这两个子问题都可以用递归的方式解决。