# 4Sum_018

###### tags: `cycle04_map_hashtable`,`leetcode`,`recursion`,`medium`

**4Sum**

>ref: https://leetcode.com/problems/4sum/
>git: https://github.com/chmonk/leetCodeTraining/blob/dev/src/cycle04_map_hashtable/fourSum_018.java
>
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.

You must write an algorithm with O(log n) runtime complexity.

>Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

>Example 2:
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

>Constraints:
1 <= nums.length <= 200
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9

>1. recursiong深度為n-2
>2. 高次數降解成低次數

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

		Arrays.sort(nums); //大小有序減少複雜度

		return ksum(nums, target, 0, 4);
	}

	private List<List<Integer>> ksum(int[] nums, int target, int idx, int n) {

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

		if (idx >= nums.length)
			return res;

		if (n > 2) {
                       //依據目前idx數值修改target,recursion到後續參數
			for (int i = idx; i < nums.length - n + 1; i++) {

				List<List<Integer>> temp = ksum(nums, target - nums[i], i + 1, n - 1);

				if (!temp.isEmpty()) {
                                       //有解時生成數組
					for (List<Integer> ans : temp) {
						ans.add(0, nums[i]);
					}
				}
				res.addAll(temp);

				while (nums[i] == nums[i + 1] && (i < nums.length - n + 1)) {
                             //重複條件 1.數值相同 且 目前idx未到尾端限制:idx<總idx-當下剩餘之n 
					i++;
				}
			}
		} else {

			// 當n==2時 2 pointer找尋符合數組
			int start = idx;
			int last = nums.length - 1;

			while (start < last) {
				int sum = nums[start] + nums[last];
				if (sum == target) {
					// res.add((ArrayList<Integer>)Arrays.asList(nums[start++], nums[last--])); 
                                      // Arrays.asList() retrun List<T> which is subclass of Arrays.LIST can't be cast as arraylist or linkedList
					res.add(new ArrayList<>(Arrays.asList(nums[start++], nums[last--])));
                    
                                     //重複數組
					while (start < last && nums[start] == nums[start - 1]) {
						start++;
					}
                                     //重複數組
					while (start < last && nums[last] == nums[last + 1]) {
						last--;
					}
				} else if (sum > target) {
					last--;
				} else {
					start++;
				}
			}

		}

		return res;
	}