Print power set


  • 0
    L

    print all combinations of a set. for example, there is an array {1, 2, 3}, its power set is:

    {#}
    {1}  {2}  {3}
    {1, 2}  {1, 3}  {2, 3}
    {1, 2, 3}
    

    there are at least two methods.


  • 6
    S
    private static void getPowerSet(int[] arr) {
    
    		int len = arr.length;
    		int total = 1<<len;
    		for (int i = 0; i < total; i++) {
    			
    			for (int j = 0; j < len; j++) {
    				//Printing all elements for which there is a bit one in i
    				if((i & (1<<j)) != 0){
    					System.out.print(arr[j]);
    				}
    			}
    			System.out.print("\n");
    		}
    		
    	}

  • 0
    J
    void getPowerSet(const vector<int>& arr)
    {
    	vector<vector<int>> results = {{}};
    	for (auto nNumber : arr) {
    		vector<vector<int>> addtionResults = results;
    		for (auto resultCopy : addtionResults) {
    			resultCopy.push_back(nNumber);
    			copy(resultCopy.begin(), resultCopy.end(), std::ostream_iterator<int>(std::cout, ""));
    			printf("\n");
    			results.push_back(resultCopy);
    		}
    	}
    }
    

  • 0
    C
    import java.util.Scanner;
    /**
     * Created by Cai on 2016/9/22.
     */
    public class text1 {
            public static void main(String []args){
                new text1().run();
            }
            public void run(){
                Scanner scanner = new Scanner(System.in);
                System.out.println("please enter the starNum:");
                int startNum = scanner.nextInt();
                System.out.println("please enter the endNum");
                int endNum = scanner.nextInt();
                System.out.println("{#}");
                for(int i = startNum ; i <= endNum; i ++){
                    String tempStr = "{ " + i + ",";
                    printStr(tempStr);
                    int tempI = i;
                    goOn(++ tempI, endNum, tempStr);
                }
            }
            public void goOn(int start, int end, String str){
                for(int i = start; i <= end; i ++){
                    String temp = str;
                    temp += " " + i + ",";
                    printStr(temp);
                    int tempI = i;
                    goOn(++ tempI, end, temp);
                }
            }
            public void printStr(String str){
                str = str.substring(0, str.length() -1) + "}";
                System.out.println(str);
            }
    }
    

    0_1474543022725_微信截图_20160922191617.png


  • 0
    B

    I have a simple, one-liner python solution to it.

        def printAllPower(self, s):
            ans=[[]]
            for element in s:
                ans=[x+[element] for x in ans]+ans
            print str(ans)[1:-1].replace('[','{').replace(']','}')
    

  • 0
    L

    @LucasDove

    My dfs solution.

    void DFS(vector<int>&vec, vector<vector<int>>& res, vector<int>& tmp, int len, int index) {
        if (index >= len) {
            res.push_back(tmp);
            return;
        }
        tmp.push_back(vec[index]);
        DFS(vec, res, tmp, len, index + 1);
        tmp.pop_back();
        DFS(vec, res, tmp, len, index + 1);
    }
    
    vector<vector<int>> getPowerSet(vector<int>& vec) {
        vector<vector<int>> res;
        if (vec.empty()) return res;
        int len = vec.size();
        vector<int> tmp;
        DFS(vec, res, tmp, len, 0);
        return res;
    }
    
    int main() {
        vector<int> vec = {1, 2, 3};
        auto ans = getPowerSet(vec);
        for (auto &item : ans) {
            for (auto &num : item) cout << num <<  " " ;
            cout << endl;
        }
    }
    

Log in to reply
 

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