14ms c++ soluton


  • 0
    Z

    my 14ms c++ solution

    	static bool bigger(int i, int j)
    {
    	return (i > j);
    }
    
    // 具有重复值的数据的子集
    vector<vector<int>> get_subsets_dup(vector<int> &data, int pos)
    {
    	vector<vector<int>> ret;
    	vector<int> t;
    
    	if (pos >= data.size())	return ret;
    
    	// 得到new pos
    	int new_pos = pos + 1;
    	while (new_pos < data.size() && data[new_pos] == data[pos])	new_pos++;
    
    	// 加入[pos, new_pos)区间可能的子集
    	t.clear();
    	for (int i = 0; i < new_pos - pos; i++){
    		t.push_back(data[pos]);
    		ret.push_back(t);
    	}
    
    	// 获取右边节点组成的有效子集
    	vector<vector<int>> next_ret = get_subsets_dup(data, new_pos);
    	for (vector<vector<int>>::iterator it = next_ret.begin(); it != next_ret.end(); ++it){
    		t = *it;
    		ret.push_back(t);
    
    		// 加入n个可能产生的子集
    		for (int i = 0; i < new_pos - pos; i++){
    			t.push_back(data[pos]);
    			ret.push_back(t);
    		}
    	}
    
    	return ret;
    }
    
    vector<vector<int> > subsetsWithDup(vector<int> &S) 
    {
    	// 排序
    	sort(S.begin(), S.end(), bigger);
    
    	// 递归调用
    	vector<vector<int>> ret = get_subsets_dup(S, 0);
    	vector<int> t;
    
    	ret.push_back(t);
    	return ret;
    }

Log in to reply
 

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