子集-ii

//用尽量简洁的代码来描述回溯法/深度优先遍历
class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        sort(S.begin(),S.end());
        dfs(S,0);
        return result;
    }
    void dfs(vector<int> set, int start){
        result.push_back(tmp);
        for(int i = start; i < set.size(); ++ i){
            tmp.push_back(set[i]);
            dfs(set,i+1);
            while(i<set.size()-1 && set[i+1]==set[i]) ++i;//比subset1多出的一行
            tmp.pop_back();
        }
    }
private:
    vector<vector<int> > result;
    vector<int> tmp;
};

// 递归，和subseti就多了一个判断而已，碰到和上一个数相等则跳过
import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    ArrayList<ArrayList<Integer>> listAll = new ArrayList<>();

    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
        if (num == null || num.length <= 0)
            return listAll;
        ArrayList<Integer> list = new ArrayList<>();
        Arrays.sort(num);

        Findsubset(num, 0, list);

        return listAll;
    }

    public void Findsubset(int[] set, int start, ArrayList<Integer> list) {
        listAll.add(new ArrayList<>(list));

        for (int i = start; i < set.length; i++) {
            if (i > start && set[i] == set[i - 1])
                continue;
            list.add(set[i]);
            Findsubset(set, i + 1, list);
            list.remove(list.size() - 1);
        }
    }
}

/**
    思路：动态规划思想：s中的i位置的元素存在分为两种情况：在子集中，不在子集中，
只要在当前的res数组中加入或者不加入该元素，直至s全部元素的情况都考虑完成，在去
除重复示例即为正确答案
**/
class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &s) {
        sort(s.begin(), s.end());
        vector<vector<int>> res;
        //vector<int> vec;
        for (int i = 0; i < s.size(); i++)
        {
            if (res.empty())
            {
                res.push_back({});
                res.push_back({ s.at(0) });
                continue;
            }
            int size = res.size();
            for (int j = 0;j<size;j++)
            {
                vector<int> v(res[j]);
                v.push_back(s.at(i));
                res.push_back(v);
            }
        }
        set<vector<int>> sets(res.begin(), res.end());
        vector<vector<int>> vv(sets.begin(), sets.end());
        return vv;
    }
};

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> res=new LinkedHashSet<List<Integer>>();
		int totalNumber=1<<nums.length;
		for(int i=0;i<totalNumber;i++){
			List<Integer> temp=new ArrayList<Integer>();
			for(int j=0;j<nums.length;j++){
				if(((i>>j)&1)==1)
					temp.add(nums[j]);
			}
			res.add(temp);
		}
		ArrayList<ArrayList<Integer>> finalres=new ArrayList<ArrayList<Integer>> ();
		for(List<Integer> temp:res){
			finalres.add((ArrayList<Integer>) temp);
		}
		return finalres;
    }
}

/*
 *	思路：对于num[i]元素，将该元素加到num[i-1]生成的子集的后面，生成一些新的子集，将这些子集加入到总的结果中
 */

public class Solution {
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
		//先对num排序
		Arrays.sort(num);
		//保存已经添加的子串，防止重复添加
		Set<ArrayList<Integer>> s = new HashSet<>();
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < num.length; i++) {
        	if (i == 0) {
        		ArrayList<Integer> empty = new ArrayList<>();
        		ans.add(empty);	//空串
        		s.add(empty);
        		ArrayList<Integer> one = new ArrayList<>();
        		one.add(num[i]);
        		ans.add(one);
        		s.add(one);
        	} else {
        		ArrayList<ArrayList<Integer>> newSubSets = new ArrayList<>();
				//根据原有子集加上当前整数生成新的子集
        		for (ArrayList<Integer> oldSubSet : ans) {
        			ArrayList<Integer> newSubSet = new ArrayList<>(oldSubSet);
        			newSubSet.add(num[i]);
        			if (!s.contains(newSubSet)) {
        				s.add(newSubSet);
        				newSubSets.add(newSubSet);
        			}
        		}
        		ans.addAll(newSubSets);
        	}
        }
        return ans;
    }
}

// 回溯
class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<int> temp;
        DFS(nums, 0, temp);
        return res;
    }
    void DFS(vector<int>& nums, int index, vector<int>& temp)
    {
        res.push_back(temp);
        for(int i = index; i < nums.size(); ++i)
        {
            if(i > index && nums[i] == nums[i-1]) continue;   // 去重
            temp.push_back(nums[i]);
            DFS(nums, i + 1, temp);
            temp.pop_back();
        }
    }
};

class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        sort(S.begin(), S.end());
        set<vector<int> > result;         for(int i=0;i<=S.size();i++)          {             vector<int> p;             Fun(result, p, 0, i, S);         }         return vector<vector<int> > (result.begin(), result.end());
    }
    
    void Fun(set<vector<int> > &result, vector<int> &p, int k, int count, vector<int> &S)
    {
        if(count == 0)
        {
            result.insert(p);
            return;         }         if(k >= S.size())             return;                  p.push_back(S[k]);         Fun(result, p, k+1, count-1, S);         p.pop_back();         Fun(result, p, k+1, count, S);     }
     
};

class Solution {
public:
  vector<vector<int> > subsetsWithDup(vector<int> &S) {
    sort(begin(S), end(S));
    
    vector<vector<int>> ans;
    vector<int> subset;
    function<void(int)> dfs = [&](int p) -> void {
      ans.emplace_back(subset);
      for (int i = p; i < S.size(); ++i) {
        if (i > p && S[i] == S[i - 1]) continue;
        subset.emplace_back(S[i]);
        dfs(i + 1);
        subset.pop_back();
      }
    };
    
    dfs(0);
    return ans;
  }
};

public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] nums) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
		if (nums == null || nums.length < 1)
			return res;
		Arrays.sort(nums);
		ArrayList<Integer> list = new ArrayList<Integer>();
		solve(nums, 0, res, list);
		return res;
	}

	private void solve(int[] nums, int start, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> list) {
		res.add(new ArrayList<Integer>(list));
		if (start >= nums.length)
			return;
		for (int i = start; i < nums.length; i++) {
			if (i > start && nums[i] == nums[i - 1])
				continue;
			list.add(nums[i]);
			solve(nums, i + 1, res, list);
			list.remove(list.size() - 1);
		}
	}

   //类似字符的所有组合的方法来递归，采用set排除重复子序列
   void subsetWithDup_aux(set<vector<int>> &sv, vector<int>& path, int index, int count,
					   vector<int> &S){	
        if (count == 0){
            sv.insert(path);
            return;
        }
        if (index >= S.size())
            return;
        path.push_back(S[index]);
        subsetWithDup_aux(sv, path, index + 1, count - 1, S);
        path.pop_back();
        subsetWithDup_aux(sv, path, index + 1, count, S);
    }

    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        sort(S.begin(), S.end());
        set<vector<int>> sv;
        for (int i = 0; i <= S.size(); i++){
            vector<int> path;
            subsetWithDup_aux(sv, path, 0, i, S);
        }
        return vector<vector<int>>(sv.begin(), sv.end());
    }

To solve this problem, it is helpful to first think how many subsets are there. If there is no duplicate element, the answer is simply 2^n, where n is the number of elements. This is because you have two choices for each element, either putting it into the subset or not. So all subsets for this no-duplicate set can be easily constructed:
num of subset

• (1 to 2^0) empty set is the first subset
• (2^0+1 to 2^1) add the first element into subset from (1)
• (2^1+1 to 2^2) add the second element into subset (1 to 2^1)
• (2^2+1 to 2^3) add the third element into subset (1 to 2^2)
• ....
• (2^(n-1)+1 to 2^n) add the nth element into subset(1 to 2^(n-1))

Then how many subsets are there if there are duplicate elements? We can treat duplicate element as a spacial element. For example, if we have duplicate elements (5, 5), instead of treating them as two elements that are duplicate, we can treat it as one special element 5, but this element has more than two choices: you can either NOT put it into the subset, or put ONE 5 into the subset, or put TWO 5s into the subset. Therefore, we are given an array (a1, a2, a3, ..., an) with each of them appearing (k1, k2, k3, ..., kn) times, the number of subset is (k1+1)(k2+1)...(kn+1). We can easily see how to write down all the subsets similar to the approach above.

class Solution { public: vector<vector<int> > subsetsWithDup(vector<int> &S) { vector<vector<int> > totalset = {{}};
        sort(S.begin(),S.end()); for(int i=0; i<S.size();){ int count = 0; // num of elements are the same while(count + i<S.size() && S[count+i]==S[i])  count++; int previousN = totalset.size(); for(int k=0; k<previousN; k++){ vector<int> instance = totalset[k]; for(int j=0; j<count; j++){
                    instance.push_back(S[i]);
                    totalset.push_back(instance);
                }
            }
            i += count;
        } return totalset;
        }
};

class Solution {
public:
    void func(vector<vector<int>> &ret,int start,vector<int> &S,vector<int> &temp){
        ret.push_back(temp);
        for(int i=start;i<S.size();i++){
            temp.push_back(S[i]);
            func(ret,i+1,S,temp);
            while(i<S.size()-1&&S[i+1]==S[i]) i++;
            temp.pop_back();
        }
    }
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        sort(S.begin(),S.end());
        vector<vector<int>> ret;
        vector<int> temp;
        func(ret,0,S,temp);
        return ret;
    }
};

深度优先遍历，通过set进行去重：

//
// Created by jt on 2020/8/25.
//
class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        sort(S.begin(), S.end());
        vector<int> vec;
        set<vector<int> > sv;
        dfs(S, vec, sv, 0);
        return vector<vector<int> >(sv.begin(), sv.end());
    }
 
    void dfs(vector<int> &S, vector<int> vec, set<vector<int> > &sv, int begin) {
        if (begin >= S.size()) { sv.insert(vec); return; }
        dfs(S, vec, sv, begin + 1);
        vec.push_back(S[begin]);
        dfs(S, vec, sv, begin + 1);
    }
};