3sum-closestDP.dart (988B)
1 //This solution uses DP to recursively break down the problem and return 2 //the result. This is not a very good solution because there is not 3 //a lot of stuff to memoize so it is not super efficient. 4 5 class Val{ 6 int val = 0; 7 int distance = 0; 8 Val(int distance_, int val_){ 9 val = val_; 10 distance = distance_; 11 } 12 } 13 14 class Solution { 15 int threeSumClosest(List<int> nums, int target) { 16 int close = (closest(nums, target, 0, 0).val); 17 return close; 18 } 19 Val closest(List<int> nums , int target , int depth, int val){ 20 if(depth == 3){ 21 return new Val(target , val); 22 } 23 Val ret = new Val(1000000000, 0); 24 for(int i = 0 ; i < nums.length ; ++i){ 25 List<int> new_nums = List.from(nums); 26 int current = new_nums[i]; 27 new_nums.removeAt(i); 28 Val return_val = closest(new_nums, target - current, depth + 1, val + current); 29 if(return_val.distance.abs() < ret.distance.abs()){ 30 ret = return_val; 31 } 32 } 33 return ret; 34 } 35 }