순열과 조합

코딩문제에서 간간히 나오는 순열과 조합, 그 원소 뽑기 코드 작성법이다.

---

46. Permutation - LeetCode

class Solution {
   public List<List<Integer>> permute(int[] nums) {
   // permutate logic
   Set<List<Integer>> ans = new HashSet<>();
   List<Integer> cur = Arrays.asList(Arrays.stream(nums).boxed().toArray(Integer[]::new));  
   permutation(ans, cur, 0);
   
   return new ArrayList(ans);
   }

   public void permutation(Set<List<Integer>> ans, List<Integer> cur, int r) {
       
       if (r == cur.size()) {
           return;
       }

       for (int i = 0; i < cur.size(); i++) {
           Collections.swap(cur, r, i);
           // ans.add(cur);  --> 문제가 많았던
           // 
           ans.add(new ArrayList(cur)); //--> 부분
           //
           permutation(ans, cur, r + 1);
           Collections.swap(cur, r, i);
       }
   }

   
}

아래의 조합은 강의를 통해서 배운 코드 작성법이고, 순열은 직접 짜본 코드이다. 그런데 제대로 HashSet의 사이즈가 증가하는데 막상 코드를 찍어보면 이상하게 나오길래 뭐가 문젠지 싶어서 한참을 헤멨다.

해시셋을 프린트로 찍어보면 저런식으로 나와버리길래 이게 뭐지??? 싶었다.

그런데 해설 코드를 보다보니, 나와 코드 구성은 다르지만 Collections 에 아이템을 넣을 때 new ArrayList 로 새롭게 객체를 만들어서 넣길래 나도 위의 코드에서 보듯이 그렇게 코드를 수정했더니

결과가 제대로 나오더라. 아직 공부가 부족한것 같다.

아래는 리트코드에서 제공하는 순열 답안.

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        backtrack(new ArrayList<>(), ans, nums);
        return ans;
    }
    
    public void backtrack(List<Integer> curr, List<List<Integer>> ans, int[] nums) {
        if (curr.size() == nums.length) {
            ans.add(new ArrayList<>(curr));
            return;
        }
        
        for (int num: nums) {
            if (!curr.contains(num)) {
                curr.add(num);
                backtrack(curr, ans, nums);
                curr.remove(curr.size() - 1);
            }
        }
    }
}

---

77. Combinations - LeetCode

class Solution {
    public List<List<Integer>> combine(int n, int k) {
    // combination logic
    int[] arr = IntStream.rangeClosed(1, n).toArray();
    boolean[] visited = new boolean[arr.length];
    List<List<Integer>> ans = new ArrayList<>();
    combination(ans, arr, visited, k, 0);

    return ans;
    }

    public void combination(List<List<Integer>> answer, int[] arr, boolean visited[], int depth, int r) {
        
        if (depth == 0) {
            List<Integer> t = new ArrayList<>();
            for (int i = 0; i < visited.length; i++) {
                if (visited[i]) {
                    t.add(arr[i]);
                }
            }

            answer.add(t);
            return;
        }

        if (r == visited.length) {
            return;
        }

        visited[r] = true;
        combination(answer, arr, visited, depth - 1, r + 1);

        visited[r] = false;
        combination(answer, arr, visited, depth, r + 1);
    }
     
}

아래는 리트코드에서 제공하는 조합 코드 답안.

class Solution {
    private int n;
    private int k;
    
    public List<List<Integer>> combine(int n, int k) {
        this.n = n;
        this.k = k;
        List<List<Integer>> ans = new ArrayList<>();
        backtrack(new ArrayList<>(), 1, ans);
        return ans;
    }
    
    public void backtrack(List<Integer> curr, int firstNum, List<List<Integer>> ans) {
        if (curr.size() == k) {
            ans.add(new ArrayList<>(curr));
            return;
        }
        
        int need = k - curr.size();
        int remain = n - firstNum + 1;
        int available = remain - need;
        
        for (int num = firstNum; num <= firstNum + available; num++) {
            curr.add(num);
            backtrack(curr, num + 1, ans);
            curr.remove(curr.size() - 1);
        }

        return;
    }
}