Java backtracking solution for K-sum beat 94%
Some tips:\n1) avoid sum cases by viewing nums[start]k and nums[end]k \n2) when backtracking, first add nums[i] to current list, after that then remove\n\nOne C
Some tips:\n1) avoid sum cases by viewing nums[start]*k and nums[end]*k \n2) when backtracking, first add nums[i] to current list, after that then remove\n\nOne C++ Reference: http://bangbingsyb.blogspot.hk/2014/11/leetcode-4sum.html \n\n    public class Solution {\n        public List<List<Integer>> fourSum(int[] nums, int target) {\n            List<List<Integer>> result = new ArrayList<List<Integer>>();\n            Arrays.sort(nums);\n            kSum(result, new ArrayList<Integer>(), nums, target, 4, 0, nums.length-1);\n            return result;\n        }\n    \n        private void kSum(List<List<Integer>> result,List<Integer> cur,int[] nums, int target,int k,int start, int end){\n            if(k == 0 || nums.length==0 || start>end) return;\n            if(k == 1){\n                for (int i = start; i <= end ; i++) {\n                    if(nums[i] == target){\n                        cur.add(nums[i]);\n                        result.add(new ArrayList<Integer>(cur));\n                        cur.remove(cur.size()-1);\n                    }\n                }\n                return;\n            }\n    \n            if(k == 2){ // 2 sum\n                int sum;\n                while (start < end){\n                    sum = nums[start]+nums[end];\n    \n                    if(sum == target){\n                        cur.add(nums[start]);\n                        cur.add(nums[end]);\n                        result.add(new ArrayList<Integer>(cur));\n                        cur.remove(cur.size()-1);\n                        cur.remove(cur.size()-1);\n    \n                        //avoid duplicate\n                        while(start < end && nums[start] == nums[start+1]) ++start;\n                        ++start;\n                        while(start < end && nums[end] == nums[end-1]) --end;\n                        --end;\n                    }else if(sum < target){\n                        //avoid duplicate\n                        while(start < end && nums[start] == nums[start+1]) ++start;\n                        ++start;\n                    }else{\n                        while(start < end && nums[end] == nums[end-1]) --end;\n                        --end;\n                    }\n                }\n                return;\n            }\n    \n            //\u907f\u514d\u4e00\u4e9b\u4e0d\u5fc5\u8981case\n            if(k*nums[start] > target || k*nums[end]<target) return;\n    \n            // k > 2 : choose nums[i] and do k-1 sum on the rest at right\n            for (int i = start; i <= (end-k+1) ; i++) {\n                // avoid duplicate\n                if(i>start && nums[i]==nums[i-1]) continue;\n                // \u91cd\u70b9\n                if(k*nums[i] <= target) { //\u907f\u514d\u6389\u4e00\u4e9b\u4e0d\u5fc5\u8981case\n                    cur.add(nums[i]);\n                    kSum(result, cur, nums, target - nums[i], k - 1, i + 1, end);\n                    cur.remove(cur.size() - 1);\n                }\n            }\n    \n        }\n    }
['Backtracking']