Simple C++ backtracking solution, easy to understand


  • 0
    G
    class Solution {
    public:
      vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > res;
        vector<int> tmp;
        perm(tmp,num,res);
        return res;
      }
    
      void perm(vector<int> tmp, vector<int> num, vector<vector<int> > & res){
        if(num.size() == 0){
            res.push_back(tmp);
        }
        for(int i = 0; i<num.size(); i++){
            tmp.push_back(num[i]);
            int t = num[i];
            num.erase(num.begin()+i);
            perm(tmp,num,res);
            tmp.pop_back();
            num.insert(num.begin()+i,t);
        }
      }
    };

  • 0
    L

    vector<vector<int> > permute(vector<int> &nums)

    {

      	vector<int> ss;
    vector<vector<int>> res;
    res.push_back(ss);
    
    for (size_t i = 0; i < nums.size(); ++i){
    	// expand the old res matrix;
    	if (res.size() == 1 && res[0].size() == 0){
    		res[0].push_back(nums[0]);
    		continue;
    	}
    	else {
    		size_t old_sz = res.size();
    		for (int j = 0; j < old_sz*(res[0].size() + 1); j = j + res[0].size()+1){
    			for (int k = 0; k < res[0].size(); ++k){
    				res.insert(res.begin()+j,res[j]);
    			}
    		}
    		
    	}
    
    	// add new elements
    	int persz = res[0].size() + 1;
    	for (int z = 0; z < res.size(); ++z){
    		res[z].insert(res[z].begin() + z%persz, nums[i]);
    	}
    
    }
    
    return res;
    }

  • 1
    M

    It's actually not easy to understand the code at all, could you add some comment or at least add some description about your idea?


  • 1
    N

    key point is that obviously,
    num.erase(num.begin()+i);
    num.insert(num.begin()+i,t);
    and simple permutation. done.
    Everybody knows it.

    I know what your point is, but I think this code just shows the flow of the mathematical approach. Although, manipulating vector container collapse everything, but the flow of idea is most intuitive.


Log in to reply
 

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