leetcode:Subsets

Given a set of distinct integers, S, 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 S =  [1,2,3] , a solution is:
    [
      [3],
      [1],
      [2],
      [1,2,3],
      [1,3],
      [2,3],
      [1,2],
      []
    ]
    제목 주소:https://oj.leetcode.com/problems/subsets/
    문제 해결 방법:
    이 문제는 두 가지 해법을 풀었다.
    해법 1:
    S에서 원소를 추가할 때마다 다음 층의 집합 = 이전 층의 집합 + 이전 층의 집합 뒤에 새로 추가된 원소를 추가하기 때문이다.다음과 같습니다.
    0----------[ ]
    1----------[ ] [1]
    2----------[ ] [1] [2] [1 2]
    3----------[ ] [1] [2] [1 2] [3] [1 3] [2 3] [1 2 3]
    .........
    코드:
    class Solution {
    public:
        vector > subsets(vector &S) {
            sort(S.begin(),S.end());
    		
    		vector > ret(1);
    		for(int i=0;i tmp=ret[j];
    				tmp.push_back(S[i]);
    				ret.push_back(tmp);
    			}
    		}
    		return ret;
        }
    };
    해법 2:
    역귀+거슬러 올라가는 방법으로 이 방법은 코드를 보면 비교적 뚜렷할 수 있다.다른 사람의 코드를 참고했습니다.
    class Solution {
    public:
    	vector > ret;
        vector > subsets(vector &S) {
            ret.clear();
    		sort(S.begin(),S.end());
    
    		vector tmpans;
    		dfs(S,0,tmpans);
    		return ret;
        }
    private:
    	void dfs(vector &s,int loc,vector &tmp){
    		if(loc==s.size()){
    			ret.push_back(tmp);
    			return;
    		}
    		
    		tmp.push_back(s[loc]);
    		dfs(s,loc+1,tmp);
    		tmp.pop_back();
    		dfs(s,loc+1,tmp);
    	}
    };

    좋은 웹페이지 즐겨찾기