Combination Sum总结

关于组合的题目我们一般用回溯法来解决。我的理解回溯法就是按照要求一直找下去，如果找到一个结果就把这个结果记录下来，然后返回上一层，如果有其它路线可以走就继续尝试，如果没有，就继续返回上一层。回溯的实现一般用递归来完成。这里介绍一下关于组合的问题，以及它的一些延伸。

1，Combination
给定两个正整数n和k，返回所有长度为k的组合，组合中的元素为1...n。
例如：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

很明显我们要用链表来记录结果，通过链表的大小来判断是否继续找下去，如果链表长度已经为k，那么就记录这个结果，返回，然后把链表的长度减去1，这样可以继续找其他的结果。当链表的size小于k的时候，我们就继续找下去，知道长度为k。
代码如下：

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> llist = new ArrayList<List<Integer>>();
        LinkedList<Integer> list = new LinkedList<Integer>();
        if(k > n) return llist;
        combination(1, n, k, list, llist);
        return llist;
    }
    
    private void combination(int start, int n, int k, LinkedList<Integer> list, List<List<Integer>> llist) {
        if(list.size() == k) {
            llist.add(new LinkedList<Integer>(list));
            return;
        }
        for(int i = start; i <= n; i++) {
            if(list.size() < k) {
                list.add(i);
                combination(i + 1, n, k, list, llist);
                list.removeLast();
            }
        }
    }
}

2，Combination Sum
给定一个数组number[] 和一个目标元素target，在数组中找出所有可能的组合，每个组合中元素的和为target，每个元素可以重复使用。
例如：number[] = {2, 3, 6, 7} target = 7
输出：[7], [2, 2, 3]

我们仍然使用回溯法，这次回溯的条件变为元素的和为target，即当我们遍历的元素的和为target时，我们就找到了一个结果，就把这个结果记录下来，然后返回上一层，继续查找其他结果，不要忘记返回后把链表的长度减1，要不然就不叫回溯了。代码如下：

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> llist = new ArrayList<List<Integer>>();
        LinkedList<Integer> list = new LinkedList<Integer>();
        if(candidates == null) return llist;
        Arrays.sort(candidates);
        int end = candidates.length;
        combinateSum(0, end, candidates, target, list, llist);
        return llist;
    }
    
    public void combinateSum(int start, int end, int[] candidates, int target, LinkedList<Integer> list, List<List<Integer>> llist) {
        for(int i = start; i < end; i ++) {
            if(target - candidates[i] > 0) {
                list.add(candidates[i]);
                combinateSum(i, end, candidates, target - candidates[i], list, llist);
                list.removeLast();
            } else if(target == candidates[i]){
                list.add(candidates[i]);
                if(!llist.contains(list))
                    llist.add(new LinkedList<Integer>(list));
                list.removeLast();
            } else {
                return;
            }
        }
    }
}

3，Combination Sum2
给定一个数组numbers[] 和一个目标元素target，从数组中找出所有可能的组合，使组合中元素的和为target，每个元素只能使用一次。
例如：number[] = {10,1,2,7,6,1,5}; target = 8;
输出：
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

这道题是combination sum的变形，关键一点时每个元素只能使用一次，只要我们在往下找的时候，不重复当前的元素就可以保证每个元素只能使用一次。代码如下：

public class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> llist = new ArrayList<List<Integer>>();
        LinkedList<Integer> list = new LinkedList<Integer>();
        if(candidates == null) return llist;
        Arrays.sort(candidates);
        combinateSum2(0, target, candidates, list, llist);
        return llist;
    }
    
    private void combinateSum2(int start, int target, int[] candidates, LinkedList<Integer> list, List<List<Integer>> llist) {
        for(int i = start; i < candidates.length; i++) {
            if(target - candidates[i] > 0) {
                list.add(candidates[i]);
                combinateSum2(i + 1, target - candidates[i], candidates, list, llist);
                list.removeLast();
            }else if(target == candidates[i]) {
                list.add(candidates[i]);
                if(!llist.contains(list))
                    llist.add(new LinkedList<Integer>(list));
                list.removeLast();
            } else {
                return;
            }
        }
    }
}

4，Combination sum3
给定一个数组numbers[] ={1,2,3,4,5,6,7,8,9}, 一个目标元素target，一个正整数k。输出所有可能的组合，使组合的长度为k，并且组合中元素的和为target，数组中每个元素只能使用一次。
例如：k = 3, target = 9;
输出：[[1,2,6], [1,3,5], [2,3,4]]

这道题与sum2的区别仅在于多了一个限定的长度，因此我们在寻找结果的时候加上一个判断当前组合长度的条件就可以了。代码如下：

public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> llist = new ArrayList<List<Integer>>();
        LinkedList<Integer> list = new  LinkedList<Integer>();
        combinateSum3(1, k, n, list, llist);
        return llist;
    }
    
    private void combinateSum3(int start, int k, int n, LinkedList<Integer> list, List<List<Integer>> llist) {
        for(int i = start; i <= 9; i++) {
            if(n - i > 0 && list.size() < k) {
                list.add(i);
                combinateSum3(i + 1, k, n - i, list, llist);
                list.removeLast();
            } else if(n == i && list.size() == k - 1) {
                list.add(i);
                llist.add(new LinkedList<Integer>(list));
                list.removeLast();
            } else {
                return;
            }
        }
    }
}