程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode78:Subsets

LeetCode78:Subsets

編輯:C++入門知識

LeetCode78:Subsets


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

Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,3], a solution is:

[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

這道題可以使用兩種方法求解,一是使用位操作,另外是使用深度優先搜索和回溯,但是我只想出了位操作,深度優先的方法是看了Discuss後想出來的。

解法一:位操作

對於數組[1,2,3],可以用一個下標0和1表示是否選擇該數字,0表示未選擇,1表示選中,那麼每一組3個0和1的組合表示一種選擇,3位共有8種選擇,分別是:
000 對應[]
001 對應[3]
010 對應[2]
011 對應[2,3]
100 …
101
110
111
那麼上面為1的位表示數組中該位被選中。
那麼只需要遍歷0到1<< length中的數,判斷每一個數中有那幾位為1,為1的那幾位即會構成一個子集中的一個元素。

runtime:8ms

class Solution {
public:
    vector> subsets(vector& nums) {
        int length=nums.size();
        sort(nums.begin(),nums.end());
        vector > result;
        for(int i=0;i<1< tmp;
            //計算i中有那幾位為1
            for(int j=0;j

解法二:回溯法

還可以使用深度優先搜索來遍歷數組,采用回溯法來剔除元素。使用一個變量來記錄路徑,每遍歷到一個元素即表示找到一條路徑,將其加入子集中。
對於數組[1,2,3]
從1開始遞歸查詢2,3,對於2,繼續向下搜索,搜索完後將2刪除。
runtime:8ms

class Solution {
public:    
    //使用深度優先的回溯法
     vector> subsets(vector& nums) {
         vector> result;
         vector path;
         sort(nums.begin(),nums.end());
         result.push_back(path);
         dfs(nums,0,path,result);
         return result;
     }
     void dfs(vector& nums,int pos,vector & path,vector> & result)
     {
            if(pos==nums.size())
                return;

            for(int i=pos;i

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved