前言:

这几天在做LeetCode 里面有2sum, 3sum(closest), 4sum等问题, 这类问题是典型的递归思路解题。该这类问题的关键在于，在进行求和求解前，要先排序Arrays.sort()可实现，而本文则着重探讨关于KSum问题。

leetcode求和问题描写叙述(K sum problem)：

K sum的求和问题通常是这样子描写叙述的：给你一组N个数字(比方 vector num), 然后给你一个常数(比方 int target) ，我们的goal是在这一堆数里面找到K个数字，使得这K个数字的和等于target。

注意事项(constraints):

注意这一组数字可能有反复项：比方 1 1 2 3 , 求3sum, 然后 target = 6, 你搜的时候可能会得到 两组1 2 3, 1 2 3，1 来自第一个1或者第二个1, 可是结果事实上仅仅有一组。所以最后结果要去重。

引用：http://tech-wonderland.net/blog/summary-of-ksum-problems.html

KSum解决方法：

解决这类问题有两个方法：

1. 暴力法：这是最直接的简单方法。问题是这种方法在K 足够大的时候时间复杂度会竭尽无穷大，故不是有效的理想方案；

2. 递归法： 该方法是有技巧性的，关键在于寻找递归基，该问题的递归基是k = 2情况。

关于,3Sum,3Sum Closest,4Sum的解题思路和參考代码。

KSum java代码：

import java.util.ArrayList;

import java.util.Arrays;

import java.util.HashSet;

import java.util.List;

public class KSum {

    /**

     * @param args

     */

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        //int[] s = new int[] {1,0,-1,0,-2,2 };

        int[] s = new int[]{-500,-490,-471,-456,-422,-412,-406,-398,-381,-361,-341,-332,-292,-288,-272,-236,-235,-227,-207,-203,-185,-119,-59,-13,4,5,46,72,82,91,92,130,130,140,145,159,187,207,211,226,239,260,262,282,290,352,377,378,386,405,409,430,445,478,481,498};

        System.out.println(" A solution set is: ");

        List<List<Integer>> listArray = new ArrayList<List<Integer>>();

        listArray = kSum(s,-3213);

        for (int i = 0; i < listArray.size(); i++) {

            System.out.println(listArray.get(i));

        }

    }

    public static List<List<Integer>> kSum(int[] nums, int target) {

        List<List<Integer>> result = new ArrayList<List<Integer>>();

        Arrays.sort(nums);

        result = recursionRoutin(nums,0,4,0);

        return result;

    }

    public static List<List<Integer>> recursionRoutin(int[] nums,int begin,int k,int target){

        HashSet<List<Integer>> elementSet = new HashSet<List<Integer>>();

        List<List<Integer>> result = new ArrayList<List<Integer>>();

        List<List<Integer>> subResult = new ArrayList<List<Integer>>();

        //Recursion Base

        if(k == 2){

            int left = begin;

            int right = nums.length - 1;

            while(left < right){

                int sum = nums[left] + nums[right];

                if(sum == target){

                    List<Integer> taplet = new ArrayList<Integer>();

                    taplet.add(nums[left]);

                    taplet.add(nums[right]);

                    //Avoid reduplication

                    if(!elementSet.contains(taplet)){

                        result.add(taplet);

                        elementSet.add(taplet);

                    }

                    left ++;

                    right --;

                }else if(sum < target){

                    left ++;

                }else{

                    right --;

                }

            }

            return result;

        }else{

            for(int i = begin;i < nums.length - k - 1;i ++){

                subResult = recursionRoutin(nums,i + 1,k - 1,target - nums[i]);

                //System.out.println(k + " " + subResult);

                if(!subResult.isEmpty()){

                    for(int j = 0;j < subResult.size();j ++){

                        subResult.get(j).add(nums[i]);

                        result.add(subResult.get(j));

                    }

                }

            }

        }

        return result;

    }

}

參考文章：http://tech-wonderland.net/blog/summary-of-ksum-problems.html

相关代码放在个人github:https://github.com/gannyee/LeetCode/