之前看的是链表的问题，现在主要是研究关于递归的问题，对初学者来说递归问题的理解是比较困难的。我也是通过一些问题的逐步分析来进行判断和理解。

这篇博客主要是针对leetcode的某一类问题进行分析。这些是关于组合求和的问题

      1.组合总和

2.组合总和 II

3.电话号码的字母组合

1.组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。

这道问题，首先来看解集不能包含重复的组合而且每个数字可以重复使用，题目给了一个示例。

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

首先，我们将这个数组进行排序。为了保证不出现重复的组合，我们在以2为首元素的时候，只考虑2，3和,5。同理向后递推，以3为首元素的时候，只考虑3，5.。每次将数组中的数字放入栈中，如果发现当前的和与target相同，就将栈中的元素进行遍历。

public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            if(candidates.length == 0)
                return result;
           Arrays.sort(candidates);
            Stack<Integer> stack = new Stack<Integer>();
            generate(0,result,stack,0,target,candidates);
            return result;
        }

主函数如上，如果数组为空，返回一个空的链表。

算法的核心是generate方法。

private void generate(int i, List<List<Integer>> result, Stack<Integer> stack, int sum, int target,int[] candidates) {
        if(i==candidates.length || sum > target)//不符合条件循环结束
            return ;
        if(sum == target){
            List<Integer> list  = new ArrayList<Integer>();
            for(Integer num : stack){
                list.add(num);
            }
            result.add(list);
        }
        for(int index = i;index<candidates.length;index++){
            stack.push(candidates[index]);
            generate(index,result,stack,sum+candidates[index],target,candidates);
            stack.pop();
        }
    }

这个函数也是调用了递归的思想，sum用来记录当前栈中的数值总和。如果发现遍历到了数组的末尾或者发现和超过了target，那么此次方法调用返回。接下来。如果sum和target相同，那么直接将栈中的值遍历插入链表中。

可以看到接下里的for循环就是将数组中index位置的数字放入栈中，然后递归下一个数字（因为可以重复，所以下一次递归调用也是从index开始的）。如果跳出了递归函数（generate方法）。说明放入的数字导致sum值过大，所以将栈顶元素进行弹出。

2.组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。

与上题不同，数组中包含重复数字，同样解集不可以重复。所以在递归调用的时候需要对传入的index值进行判断。这道题和上一道题的思路相同，所以把代码先写出来。

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            if(candidates.length == 0)
                return result;
            Arrays.sort(candidates);
            Stack<Integer> stack = new Stack<Integer>();
            backTrace(0,candidates,target,0,result,stack);
            return result;
    }
    private void backTrace(int index, int[] candidates, int target, int sum, List<List<Integer>> result,Stack<Integer> stack) {
        if(index >candidates.length || sum>target)
            return ;
        if(sum == target){
            List<Integer> list = new ArrayList<Integer>();
            for(Integer num : stack){
                list.add(num);
            }
            result.add(list);
            System.out.println(list);
        }
        for(int i = index;i<candidates.length;i++){
            if(sum+candidates[i] > target)
                break;
            if(i > index && candidates[i] == candidates[i-1])
                continue;
            stack.push(candidates[i]);
            backTrace(i+1, candidates, target, sum+candidates[i], result, stack);
            stack.pop();
        }
}

我将核心的for循环部分粘贴出来

for(int i = index;i<candidates.length;i++){
            if(sum+candidates[i] > target)
                break;
            if(i > index && candidates[i] == candidates[i-1])
                continue;
            stack.push(candidates[i]);
            backTrace(i+1, candidates, target, sum+candidates[i], result, stack);
            stack.pop();
        }

首先这个数组是经过排序的，所以发现sum+candidates[i]超过target，那么就没有必要去遍历i之后的元素了。因为一定会只有的值和sum相加也一定会超过target（整个数组是递增的）。

其次，关于第二个if条件是为了防止重复。参考实例

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

这个数组排序后位1,1,2,5,6,7,10。target为8.当我们判断了1（index=0）和7 为结果之后。i=index=0时的backTrace方法执行完毕。此时i++为1，这个时候i>index且candidates[1] = candidates[0]。这个时候如果考虑这个1，那么就会和之后的7再次组成结果。为了防止重复，使用了这个if判断。其他的就和上道题完全相同了。

3.电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

200px-Telephone-keypad2.svg.png

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

这道题和上面两道题的思路是相通的，只不过这道题很类似于掷骰子的问题

就像将A数组中n个数和B数组中的m个数还有C数组中的j个数进行全排列得到n*m*j个结果。

public List<String> letterCombinations(String digits) {
          List<String> result = new ArrayList<String>();
          if(digits == null||"".equals(digits))
              return result;
          char[][] dictionary =  {
                  {},{},
                  {'a','b','c'},{'d','e','f'},{'g','h','i',}
                  ,{'j','k','l'},{'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}      
          };
          char[] digs = digits.toCharArray();
          Set<String> set = new HashSet<String>();
          Stack<Character> item = new Stack<Character>();
          generate(0,dictionary,digs,result,set,item);
          return result;
        }
    private void generate(int i,char[][] dictionary, char[] digs, List<String> result, Set<String> set,  Stack<Character> item) {
        if(i>=digs.length){
            if(!set.contains(item)){
                String s = "";
                for(Character c : item){
                    s+=c;
                }
                set.add(s);
                result.add(s);
            }
            return ;
        }
        int num = Integer.valueOf(digs[i])-'0';//找到对应字典中的位置
        for(int j = 0;j<dictionary[num].length;j++){
            item.push(dictionary[num][j]);
            generate(i+1, dictionary, digs, result, set, item);
            item.pop();
        }
    }