18. 4Sum
문제 링크: https://leetcode.com/problems/4sum/
n개의 정수로 이루어진 배열이 주어지면, 배열 중 네 원소를 더해 target이 되는 부분집합들의 집합을 반환하는 문제이다.
가장 먼저 떠오르는 방법은 재귀함수를 이용한 백트래킹이다.
연속된 네 개의 원소 합이 target이라면 two-pointer로 dp를 사용해도 될텐데, 그렇지 않으니 백트래킹으로 풀었다.
분기문은 선택한 원소가 네 개가 되었을 때, 합이 target이 되면 list에 추가하는 방식으로 하면 되겠다.
Solution
1. Back-tracking with recursive
각 subset은 유일해야 하므로
nums를 정렬한다.
class Solution {
List<List<Integer>> sets = new ArrayList<>();
List<Integer> subset = new ArrayList<>();
public void makeSubset(int[] nums, int index, int target) {
if(subset.size() == 4) {
int sum=0;
for(Integer num: subset) {
sum+=num;
}
if(target == sum) {
sets.add(new ArrayList<>(subset));
}
return;
}
for(int i=index; i<nums.length; i++) {
subset.add(nums[i]);
makeSubset(nums, i+1, target);
subset.remove(Integer.valueOf(nums[i]));
}
}
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
makeSubset(nums, 0, target);
return sets;
}
}주의 ) HashSet의 remove(Object O)메소드는 integer가 들어갈 경우, index로 간주하기 때문에 Integer객체로 만들어 subset.remove(Integer.valueOf(nums[i])); 이렇게 제거해야 한다.
백트래킹을 사용했는데 글쎄! 중복된 원소가 있는 배열이 주어졌을 때 중복된 리스트를 출력하는 경우가 있다.
그렇다고 중복 원소를 제거하면 안 된다.
따라서 리스트 안의 리스트들 중 중복된 리스트는 제거하는 메소드를 만들었다.
public boolean contains(List<List<Integer>> sets, List<Integer> subset) {
int index = 0;
boolean contain=false;
for(List<Integer> set: sets) {
contain = true;
index = 0;
for(Integer num: set) {
if(!num.equals(subset.get(index))) {
contain=false;
break;
}
index++;
}
if(contain) return true;
}
return contain;
}이렇게 가능한 모든 네 개의 조합을 만든 다음, 합이 target이 되는 경우를 고르고, 그 숫자 집합이 유일한지를 검사하는 코드를 작성했다.
class Solution {
List<List<Integer>> sets = new ArrayList<>();
List<Integer> subset = new ArrayList<>();
public void makeSubset(int[] nums, int index, int target) {
if(subset.size() == 4) {
int sum=0;
for(Integer num: subset) {
sum+=num;
}
if(target == sum && !contains(sets, subset)) {
sets.add(new ArrayList<>(subset));
}
return;
}
for(int i=index; i<nums.length; i++) {
subset.add(nums[i]);
makeSubset(nums, i+1, target);
subset.remove(Integer.valueOf(nums[i]));
}
}
public boolean contains(List<List<Integer>> sets, List<Integer> subset) {
int index = 0;
boolean contain=false;
for(List<Integer> set: sets) {
contain = true;
index = 0;
for(Integer num: set) {
if(!num.equals(subset.get(index))) {
contain=false;
break;
}
index++;
}
if(contain) return true;
}
return contain;
}
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
makeSubset(nums, 0, target);
return sets;
}
}결과는 TLE !
2-1. Two Pointers for 4Sum
이 문제는 3Sum과 비슷하다.
3Sum 풀이에서는 Two Sum을 loop로 감싸고, pivot에 따라 iterate하면서 target-pivot이 되는 모든 원소쌍을 찾는다.
- Two Sum 풀이에서는 hash set을 사용한다.
- Two Sum II 풀이에서는 정렬된 배열에서의 two pointers approach를 사용한다.
위와 비슷하게, 4Sum에서도 3Sum을 loop로 감쌀 수 있다.
class Solution {
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
for(int i=0; i<nums.length-1 && nums[i]<=0; i++) {
if(i!=0 && nums[i-1]==nums[i]) continue;
twoSum(nums, i);
}
return list;
}
public void twoSum(int[] nums, int i) {
Set<Integer> set = new HashSet<Integer>();
for(int j=i+1; j<nums.length; j++) {
int complement = -nums[i] - nums[j];
if(set.contains(complement)) {
list.add(Arrays.asList(complement, nums[i], nums[j]));
while(j<nums.length-1 && nums[j] == nums[j+1])
j++;
}
set.add(nums[j]);
}
}
}
2-2. Two Pointers for kSum
만약 면접관이 4Sum 문제를 풀도록 요청한다면 5Sum, 6Sum 등의 문제가 이어질 수 있다.
그들이 실제로 원하는 것은 kSum solution일 것이다.
따라서 이번에는 kSum solution으로 일반화를 해볼 것이다.
Two pointer patters은 정렬된 배열을 요구하므로 먼저 배열을 정렬한다.
(중복된 원소를 다루기엔 정렬된 배열이 수월하기 때문이다: 연속된 원소가 동일하다면 skip한다.)
3Sum에서는, single loop에서 pivot을 iterate하며 배열의 나머지 원소들에 대해 two pointers를 적용했다.
kSum에서는, k-2개의 nested loop를 iterate하며 나머지 원소들에 대해 two pointer를 적용할 것이다.
Algorithm
k-2개의 nested loop는 재귀함수를 이용하여 구현할 수 있다.
starting point와 k를 인자로 넘기고, k==2일 때 분기하여 twoSum을 호출한 후 재귀를 종료할 것이다.
- main function
- input 배열
nums를 정렬한다. start=0, k=4, target을 인자로 하여kSum을 호출한다.
- input 배열
kSumfunctionk개의 최소 원소들의 합이target보다 크거나,k개의 최대 원소들의 합이target보다 작은지 확인하고, 그럴 경우 iteration을 중단한다.
(배열은 정렬되어 있으므로 최소값은nums[start]이며, 최대값은nums[nums.length-1]이다.k가 2와 같다면,twoSum을 호출하고 result를 반환한다.start로부터 pivot값을 iterate 한다.- 만약, 현재 원소가 이전 원소와 값이 동일하다면 skip 한다.
- 재귀적으로
start=i+1, k=k-1, target=target-nums[i]인자로kSum을 호출한다. - 반환된
set에 대해nums[i]를 추가한다.
- result를 반환한다.
twoSumfunction- low pointer
lo를start에, high pointerhi를 last index에 둔다. - low pointer가 high pointer 보다 작은 원소를 가리키는 동안 two pointer approach를 수행한다.
- low pointer
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
return kSum(nums, 0, 4, target);
}
public List<List<Integer>> kSum(int[] nums, int start, int k, int target) {
List<List<Integer>> res = new ArrayList<>();
if (start == nums.length || k*nums[start] > target || k*nums[nums.length-1] < target)
return res;
if (k==2) {
return twoSum(nums, start, target);
}
for (int i=start; i<nums.length; i++) {
if (i!=start && nums[i-1]==nums[i]) continue;
for (var set : kSum(nums, i+1, k-1, target-nums[i])) {
res.add(new ArrayList<>(Arrays.asList(nums[i])));
res.get(res.size()-1).addAll(set);
}
}
return res;
}
public List<List<Integer>> twoSum(int[] nums, int start, int target) {
List<List<Integer>> res = new ArrayList<>();
int lo = start;
int hi = nums.length-1;
while (lo<hi) {
int sum = nums[lo]+nums[hi];
if (target == sum) {
res.add(Arrays.asList(nums[lo++], nums[hi--]));
while (lo<hi && nums[lo-1]==nums[lo]) lo++;
}
else if (target < sum) hi--;
else lo++;
}
return res;
}
}
3. Hash Set
Two Sum 풀이에서와 같이 Hash Set을 이용한다.
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
return kSum(nums, 0, 4, target);
}
public List<List<Integer>> kSum(int[] nums, int start, int k, int target) {
List<List<Integer>> res = new ArrayList<>();
if (start == nums.length || k*nums[start] > target || k*nums[nums.length-1] < target)
return res;
if (k==2) {
return twoSum(nums, start, target);
}
for (int i=start; i<nums.length; i++) {
if (i!=start && nums[i-1]==nums[i]) continue;
for (var set : kSum(nums, i+1, k-1, target-nums[i])) {
res.add(new ArrayList<>(Arrays.asList(nums[i])));
res.get(res.size()-1).addAll(set);
}
}
return res;
}
public List<List<Integer>> twoSum(int[] nums, int start, int target) {
List<List<Integer>> res = new ArrayList<>();
Set<Integer> set = new HashSet<>();
for (int i=start; i<nums.length; i++) {
if (!res.isEmpty() && res.get(res.size()-1).get(1)==nums[i]) continue;
int complement = target-nums[i];
if (set.contains(complement))
res.add(Arrays.asList(complement, nums[i]));
set.add(nums[i]);
}
return res;
}
}
