Accepted 20ms c++ solution use backtracking, 16 lines, similar with what is used in solving Subsets, easy understand.


  • 0

    Here is my solutions for Subsets and Subsets II.

    Based on this idea, can also solve Permutations and Permutations II.

    Accepted 20ms c++ solution use backtracking for Permutations:

    class Solution {
    public:
        std::vector<std::vector<int> > permute(std::vector<int> &nums) {
            std::vector<std::vector<int> > res;
    		std::vector<int> perm;
    		permute(res, nums, perm);
    		return res;
        }
    private:
    	void permute(std::vector<std::vector<int> > &res, std::vector<int> &nums, std::vector<int> &perm) {
    		if (nums.empty()) {
    			res.push_back(perm);
    			return;
    		}
    		for (std::size_t i = 0; i != nums.size(); ++i) {
    			int num = nums[i];
    			perm.push_back(num);
    			nums.erase(nums.begin() + i);
    			permute(res, nums, perm);
    			nums.insert(nums.begin() + i, num);
    			perm.pop_back();
    		}
    	}
    };
    

    Accepted 35ms c++ solution use backtracking for Permutations II:

    class Solution {
    public:
        std::vector<std::vector<int> > permuteUnique(std::vector<int> &nums) {
    		std::sort(nums.begin(), nums.end());
            std::vector<std::vector<int> > res;
    		std::vector<int> perm;
    		permuteUnique(res, nums, perm);
    		return res;
        }
    private:
    	void permuteUnique(std::vector<std::vector<int> > &res, std::vector<int> &nums, std::vector<int> &perm) {
    		if (nums.empty()) {
    			res.push_back(perm);
    			return;
    		}
    		for (std::size_t i = 0; i != nums.size(); ++i)
    			if (!i || nums[i] != nums[i - 1])
    			{
    				int num = nums[i];
    				perm.push_back(num);
    				nums.erase(nums.begin() + i);
    				permuteUnique(res, nums, perm);
    				nums.insert(nums.begin() + i, num);
    				perm.pop_back();
    			}
    	}
    };
    

Log in to reply
 

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