LeetCode – 4Sum (Java)
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Note: Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d) The solution set must not contain duplicate quadruplets. For example, given array S = {1 0 -1 0 -2 2}, and target = 0. A solution set is: (-1, 0, 0, 1) (-2, -1, 1, 2) (-2, 0, 0, 2) Java Solution A typical k-sum problem. Time is N to the power of (k-1). public List < List < Integer >> fourSum ( int [ ] nums, int target ) { List < List < Integer >> result = new ArrayList < List < Integer >> ( ) ; if ( nums == null || nums. length < 4 ) return result ; Arrays . sort ( nums ) ; for ( int i = 0 ; i < nums. length - 3 ; i ++ ) { if ( i != 0 && nums [ i ] == nums [ i - 1 ...