SubSets(I/II)-Using backtracking

[LeetCode-78] SubSets

Given a set of distinct integers, nums, return the possible subsets.

거슬러 올라가다

시간 복잡도 O (n^2)
공간 복잡성 O (n)
코드

public class Solution {
    public List> subSets(int[] nums) {
        List list = new ArrayList<>();
        List> res = new ArrayList<>();
        helper(nums, res, list, 0);
        return res;
    }

    private void helper(int[] nums, List> res, List list, int pos) {
        res.add(new ArrayList<>(list));
        for (int i = pos; i < nums.length; i++) {
            list.add(nums[i]);
            helper(nums, res, list, i + 1);
            list.remove(list.size() - 1);
        }
    }
}

[LeetCode-90] SbuSets II

Given a collection of integer that may contain duplicates, nums, return the possible subsets.

거슬러 올라가다반복할 때 반복 요소를 건너뛰거나 Set을 사용합니다.

시간 복잡도 O (n^2)
공간 복잡성 O (n)
사고의 방향
주의

중복원소를 포함하니 무게를 줄이는 데 주의하세요.

우선 순서.그런 다음 반복 요소를 건너뜁니다.

정렬을 사용하여 중복 요소를 제거하지 않으면 Set>을 사용할 수 있지만 먼저 정렬해야 합니다.

주의 거슬러 올라가기:list.remove(list.size() - 1);

귀환 방법 helper () 는 int 인삼pos가 필요합니다. 귀환할 때마다 현재 그룹 원소의 다음 원소 위치에서 시작하기 때문입니다.

귀속된pos 위치는 i+1이다.

결과 세트가 추가될 때마다 다른 복제본이 생성됩니다.예: res.add

코드

/**
 *   Set      。      。
 *     ：Set    List，     ，
 *   list      ，         list。
 */
public class Solution {
    public List> subSetsWithDup(int[] nums) {
        List list = new ArrayList<>();
        Set> resSet = new HashSet<>();
        Arrays.sort(nums);   //     
        helper(nums, resSet, list, 0);
        return new ArrayList>(resSet);
    }

    private void helper(int[] nums, Set> resSet, List list, int pos) {
        resSet.add(new ArrayList<>(list));
        for (int i = 0; i < nums.length; i++) {
            list.add(nums[i]);
            helper(nums, resSet, list, i + 1);
            list.remove(list.size() - 1);
        }
    }
}

/**
 *    Set，      ，           。
 */
 public class Solution {
     public List> subSetsWithDup(int[] nums) {
         List list = new ArrayList<>();
         List> res = new ArrayList<>();
         helper(nums, res, list, 0);
         return res;
     }

     private void helper(int[] nums, List> res, List list, int pos) {
         res.add(new ArrayList<>(list));
         int i = pos;
         while (i < nums.length) {
             list.add(nums[i]);
             helper(nums, res, list, i + 1);
             list.remove(list.size() - 1);
             i++;
             //       ,    i-1，      。
             while (i < nums.length && nums[i] == nums[i - 1]) {
                 i++;
             }
         }
     }
 }

[끝]