Strong Unhire solution


  • 0
    F

    Just for fun.

    public class Solution {
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            List<List<Integer>> ret = new ArrayList<>();
            Set<String> hsh = new HashSet<String>();
            Arrays.sort(nums);
            for (int i = 0; i < (1 << nums.length); i++) {
                String s = "";
                List<Integer> cur = new ArrayList<>();
                for (int j = 0; j < nums.length; j++) {
                    if (((i >> j) & 1) > 0) {
                        s += nums[j] + "#";
                        cur.add(nums[j]);        
                    }
                }
                if (!hsh.contains(s)) {
                    hsh.add(s);
                    ret.add(cur);
                }
            }
            return ret;
        }
    }
    

  • 0
    F

    Normal solution:

       vector<vector<int>> subsetsWithDup(vector<int>& nums) {
            vector<vector<int>> ret;
            vector<int> cur;
            sort(nums.begin(), nums.end());
            dfs(nums, 0, ret, cur);
            return ret;
        }
        
        void dfs(vector<int>& nums, int pos, vector<vector<int>> & ret, vector<int> cur) {
            if (pos <= nums.size()) ret.push_back(cur);
            for (int i = pos; i < nums.size(); i++) {
                if (i > pos && nums[i] == nums[i - 1]) continue;
                cur.push_back(nums[i]);
                dfs(nums, i + 1, ret, cur);
                cur.pop_back();
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.