[Java] LeetCode 491. Non-decreasing Subsequences

[Java] LeetCode 491. Non-decreasing Subsequences

 

문   제 : 

정수형 1차원 배열 nums가 주어진다.

증가하는 형태의 부분배열을 모두 구하여라.

 

{ 1 <= nums.length <= 15 }

{ -100 <= nums[i] <= 100 }

 

 

Given an integer array nums, 
return all the different possible non-decreasing subsequences 
of the given array with at least two elements. 
You may return the answer in any order.

 

Example )

Input: nums = [4,6,7,7]
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

///////////////////////////////////////////////////////

Input: nums = [4,4,3,2,1]
Output: [[4,4]]

 

---

접   근 : 

인덱스가 증가함에 따라 증가하고 있는 부분배열들을 재귀함수를 통해 모두 구한다.

겹치는 부분 배열이 있으면 안되므로 HashSet을 활용한다.

 

---

해   결 : 

결과 값을 담을 HashSet을 선언한다.

HashSet에 들어갈 Integer로 구성된 List를 선언한다.

재귀함수를 부른다.

 -> solve 함수를 작성한다.

 

---

 

HashSet을 선언한다.

Set<List<Integer>> set = new HashSet<>();

 

 

---

 

HashSet에 담길 List를 선언한다.

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

 

---

 

solve 함수를 작성한다.

 

public void solve(int[] nums, int index, List<Integer> temp, Set<List<Integer>> set, int pre){

    if(index == nums.length) { // break
        if(temp.size() >= 2) {
            set.add(new ArrayList<Integer>(temp));
        }
        return;
    }

    if(pre == -1 || nums[index] >= nums[pre]){ // 처음 or 증가하고 있는 중이면
        temp.add(nums[index]);
        solve(nums, index+1, temp, set, index); // 다음 index 검사
        temp.remove(temp.size()-1); // 추가한거 지우고 
    }
    solve(nums, index+1, temp, set, pre); // 다시 검사
}

break : 

만약 검사하고 있는 인덱스가 nums 배열의 끝에 도달했다면, 재귀함수를 종료시킨다.

여기서, 저장하고 있던 temp List의 길이가 2이상이라면, 유효한 부분배열이므로 set에 추가시켜준다.

 

처음 or 증가하고 있는 중이면 : 

List에 nums[현재 인덱스] 를 추가해준다.

그리고 나서 다음 인덱스를 검사하기위해 인덱스 값과 이전 인덱스 값에 +1을 해준 후 solve함수를 호출한다.

추가했던 값을 다시 지운다. -> 모든 부분배열을 구해야하기 때문에 현재 인덱스가 생략된 상태의 부분배열을 구하기 위함이다.

 

모든 상황 : 

인덱스만 +1 한 후 다시 solve 함수를 호출한다.

-> 이렇게 되면 pre에 저장되어 있는 값은 그대로이기 때문에 index와 pre값이 차이가 벌어지게 되고, 붙어있지 않는 부분배열도 검사할 수 있게 된다.

 

---

결   과  :

class Solution {

    public List<List<Integer>> findSubsequences(int[] nums) {
        Set<List<Integer>> set = new HashSet<>();
        List<Integer> temp = new ArrayList<>();

        solve(nums, 0, temp, set, -1);

        return new ArrayList<List<Integer>>(set);
        
    }
    public void solve(int[] nums, int index, List<Integer> temp, Set<List<Integer>> set, int pre){
        
        if(index == nums.length) { // break
            if(temp.size() >= 2) {
                set.add(new ArrayList<Integer>(temp));
            }
            return;
        }

        if(pre == -1 || nums[index] >= nums[pre]){ // 처음 or 증가하고 있는 중이면
            temp.add(nums[index]);
            solve(nums, index+1, temp, set, index); // 다음 index 검사
            temp.remove(temp.size()-1); // 추가한거 지우고 
        }
        solve(nums, index+1, temp, set, pre); // 다시 검사
    }
}