491.递增子序列

和子集类似，但不能排序去重，也就不能通过挨着的元素树层去重。

求子集，子序列都是在节点上收获结果（回溯可以不要终止条件，找到结果也不需要return），而划分，分割都是在叶子节点上获得结果，注意区分，组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。
求子集不需要终止条件，搜到底就结束了。
注意Uset仅是一层的局部变量，不需要回溯，和used数组去重需要回溯不一样，因为used是一个全局变量（通过引用传参）

//C++
class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        BackTracking(nums, 0);
        return res;
    }
    void BackTracking(vector<int>& nums, int startIndex) {
        if (path.size() > 1) {
            res.push_back(path);
            //别return，取树枝上的点
        }
        unordered_set<int> uset;
        for (int i = startIndex; i < nums.size(); i++) {
            if ((!path.empty() && nums[i] < path.back()) || (uset.find(nums[i]) != uset.end())) {
                continue;
            }
            uset.insert(nums[i]);
            path.push_back(nums[i]);
            BackTracking(nums, i + 1);
            path.pop_back();
        } 

    }
};
// C#
public class Solution {
    public IList<IList<int>> res = new List<IList<int>>();
    public List<int> path = new List<int>();
    public IList<IList<int>> FindSubsequences(int[] nums) {
        BackTracking(nums, 0);
        return res;
    }
    public void BackTracking(int[] nums, int startIndex) {
        if (path.Count >= 2) res.Add(new List<int>(path));
        HashSet<int> uset = new HashSet<int>(); 
        for (int i = startIndex; i < nums.Length; i++) {
            if ((path.Count != 0 && nums[i] < path[path.Count - 1]) || (uset.Contains(nums[i])))
                continue;
            uset.Add(nums[i]);
            path.Add(nums[i]);
            BackTracking(nums, i + 1);
            path.RemoveAt(path.Count - 1);
        }
    }
}

使用数组进行哈希，适当对-100 100的nums进行平移缩放到0-200。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        BackTracking(nums, 0);
        return res;
    }
    void BackTracking(vector<int>& nums, int startIndex) {
        if (path.size() > 1) {
            res.push_back(path);
            //别return，取树枝上的点
        }
        int used[201] = {0};
        for (int i = startIndex; i < nums.size(); i++) {
            if ((!path.empty() && nums[i] < path.back()) || used[nums[i] + 100] == 1) {
                continue;
            }
            used[nums[i] + 100] = 1;
            path.push_back(nums[i]);
            BackTracking(nums, i + 1);
            path.pop_back();
        } 

    }
};

46.全排列

全排列集合靠后的数可以重复向前选择，所以不用startIndex，这时候要注意需要进行树枝去重（错了，不是树枝，树枝是指不同位置相同值，实际上这里用的是同一个位置的元素，等同于树层去重里记录每一位元素是否被用过）避免重复。

vector可以初始化定义大小和值：构造函数(nums.size(), false)，C# List没有，但可以先定义空间，在通过Array.Fill(对象，填充内容)函数填充元素;
每一层实际都遍历了整个数字集合取分支，used数组标记了上面的树使用过的元素，跳过即可。

排列问题的不同：

每层都是从0开始搜索而不是startIndex；需要used数组记录path里都放了哪些元素了

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> used(nums.size(), false);
        BackTracking(nums, used);
        return res;
    }
    void BackTracking(vector<int>& nums, vector<bool>& used) {
        if (path.size() == nums.size()) res.push_back(path);
        for (int i = 0; i < nums.size(); i++) {
            if (used[i] == true) continue;
            used[i] = true;
            path.push_back(nums[i]);
            BackTracking(nums, used);
            used[i] = false;
            path.pop_back();
        }
    }
};
//C#
public class Solution {
    IList<IList<int>> res = new List<IList<int>>();
    List<int> path = new List<int>();
    public IList<IList<int>> Permute(int[] nums) {
        bool[] used = new bool[nums.Length];
        BackTracking(nums, used);
        return res;
    }
    public void BackTracking(int[] nums, bool[] used) {
        if (path.Count == nums.Length) {
            res.Add(new List<int>(path));
            return;
        }
        
        for (int i = 0; i < nums.Length; i++) {
            if (used[i] == true) continue;
            used[i] = true;
            path.Add(nums[i]);
            BackTracking(nums, used);
            used[i] = false;
            path.RemoveAt(path.Count - 1);
        }
    }
}

47.全排列 II

考验去重，使用uset在当前层去重，或者排序后使用used去重（注意不能用startIndex了，每次都从0开始），使用used数组效率更高一些，uset本身哈希费时间费空间。

//C++ uset去重
class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<bool> used(nums.size(), false);
        BackTracking(nums, used);
        return res;
    }
    void BackTracking(vector<int>& nums, vector<bool>& used) {
        if (path.size() == nums.size()) {
            res.push_back(path);
            return;
        }
        unordered_set<int> uset;
        for (int i = 0; i < nums.size(); i++) {
            if (used[i] == true) continue;
            if (uset.find(nums[i]) != uset.end()) continue;
            used[i] = true;
            uset.insert(nums[i]);
            path.push_back(nums[i]);
            BackTracking(nums, used);
            path.pop_back();
            used[i] = false;
        }
        
    }
};
//C# 排序后去重
public class Solution {
    IList<IList<int>> res = new List<IList<int>>();
    List<int> path = new List<int>();
    bool[] use;
    public IList<IList<int>> PermuteUnique(int[] nums) {
        use = new bool[nums.Length];
        Array.Sort(nums);
        BackTracking(nums);
        return res;
    }
    public void BackTracking(int[] nums) {
        if (nums.Length == path.Count) {
            res.Add(new List<int>(path));
            return;
        }
        for (int i = 0; i < nums.Length; i++) {
            if (use[i] == true) continue;
            if (i > 0 && nums[i] == nums[i - 1] && use[i - 1] == false) continue;
            use[i] = true;
            path.Add(nums[i]);
            BackTracking(nums);
            path.RemoveAt(path.Count - 1);
            use[i] = false;
        }
    }
}

注意use[i - 1] == false 也可以写成true，那就是树枝去重了，效率低。

[代码随想录一刷] day29 回溯算法

491.递增子序列

46.全排列

47.全排列 II