Young Tableau problem - Cormen
Young Tableau A a X b matrix is Young Tableau if all rows(from left to right…
November 17, 2020
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Notice that the solution set must not contain duplicate quadruplets.
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Input: nums = [], target = 0
Output: []
Lets take help of our two-sum problem.
private List<List<Integer>> twoSum(int[] nums, int target, int start) {
List<List<Integer>> res = new ArrayList<>();
int l = start;
int r = nums.length-1;
while (l < r) {
/**
* second conditions are for avoiding duplicates.
*/
if (nums[l] + nums[r] < target || (l > start && nums[l-1] == nums[l])) {
l++;
}
else if (nums[l] + nums[r] > target || (r < nums.length-1 && nums[r] == nums[r+1])) {
r--;
}
else {
List<Integer> t = new ArrayList<>();
t.add(nums[l]);
t.add(nums[r]);
res.add(t);
l++;
r--;
}
}
return res;
}
// -2 -1 0 0 1 2
private List<List<Integer>> helper(int[] nums, int target, int startIndex, int k) {
List<List<Integer>> res = new ArrayList<>();
if (startIndex >= nums.length || nums[startIndex] * k > target || target > nums[nums.length - 1] * k) {
return res;
}
else if (k == 2) {
return twoSum(nums, target, startIndex);
}
else {
for (int i=startIndex; i<nums.length; i++) {
//This condition is to avoid duplicates
if (i == startIndex || nums[i] != nums[i-1]) {
List<List<Integer>> res2 = helper(nums, target-nums[i], i+1, k-1);
for (List<Integer> t : res2) {
List<Integer> newRes = new ArrayList<>();
newRes.add(nums[i]);
newRes.addAll(t);
res.add(newRes);
}
}
}
}
return res;
}
public List<List<Integer>> fourSum(int[] nums, int target) {
//sorting will help in avoiding duplicates in easy manner
Arrays.sort(nums);
return helper(nums, target, 0, 4);
}
O(n^2)
Young Tableau A a X b matrix is Young Tableau if all rows(from left to right…
A number consists of digits. Example: 843. Its a 3-digit number. Radix sort…
Problem Statement Determine whether an integer is a palindrome. An integer is a…
Problem Statement Given a string s, return the maximum number of unique…
Problem Statement Given n non-negative integers a1, a2, …, an , where each…
Problem Statement Given a string s, find the longest palindromic substring in s…
Introduction This post has the complete code to send email through smtp server…
Introduction In a normal email sending code from python, I’m getting following…
Introduction In one of my app, I was using to talk to . I have used some event…
Introduction So you have a Django project, and want to run it using docker image…
Introduction It is very important to introduce few process so that your code and…
Introduction In this post, we will see a sample Jenkin Pipeline Groovy script…