回溯和递归法题目

LeetCode 332. 重新安排行程

• 此题的大部分是按照回溯法标准套路进行
  • 也就是
  • 遍历尝试DFS
  • 满足条件的修改环境
  • 递归
  • 出现结果的话直接返回
  • 没出现的话将环境复原
  • 继续尝试下一种
• 但是注意需要一个排序（因为返回字典序最小的结果）快速的从一个string出发到一个string截止并且能处理重复情况的方式
  • 使用了unordered_map<string, map<string, int>>
  • 外层map将起点映射到终点
  • 内层map将终点映射到出现过的次数

    class Solution {
    public:
        // unordered_set<int> used;
        vector<string> ret;
        unordered_map<string, map<string, int>> to;
        bool flag;
        vector<string> findItinerary(vector<vector<string>>& tickets) {
            flag = false;
            for(auto& i:tickets)
            {
                ++to[i[0]][i[1]];
            }
            
    
            vector<string> ans;
            // ans.resize(tickets.size());
            recur(tickets, ans);
            return ans;
    
        }
    
        void recur(vector<vector<string>>& tickets, vector<string>& ans)
        {
            // cout<<tickets.size()<<endl;
            int cnt = tickets.size();
            if(!ans.size())
            {
                for(auto& i : to["JFK"])
                {
                    if(i.second>0)
                    {
                        --i.second;
                        ans.push_back("JFK");
                        ans.push_back(i.first);
                        
                        recur(tickets, ans);
                        if(flag)return;
                        ans.pop_back();
                        ans.pop_back();
                        ++i.second;
                    }
                }
                return;
            }
            if(ans.size() == cnt+1)
            {
                flag = true;
                return;
            }
    
            for(auto& i : to[ans[ans.size()-1]])
            {
                if(i.second>0)
                {
                    i.second--;
                    ans.push_back(i.first);
                    // cout<<i.first<<endl;
                    recur(tickets, ans);
                    if(flag)return;
                    ans.pop_back();
                    i.second++;
                }
            }
        }
    };

Leetcode 47. 全排列II

• 关键是去重
• 还要强调的是去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了
  • 有两种去重的方式，其中一种是当目前循环的时候如果i大于起始位置而且数组中第i个的值等于第i-1个的话，则跳过i（这种去重的方式允许不同层级的回溯具有相同的元素值，因为允许在当前迭代的第一个元素的位置进入下一层）
  • 参考力扣子集II
  • 另一种方式是使用used数组来记录，跳过所有与上一个元素相同而且目前没有被使用的元素，也就是在这一层出现的重复元素。
  • 
  • 如果这个位置和上个位置相同，而且上个位置的数字在另外的分支里被使用过（也就是used[i-1] == false），那么跳过这个数字来去重
  • 在这个位置中被使用过的数字的used是true

    class Solution {
    private:
        vector<vector<int>> result;
        // vector<int> path;
        void backtracking (vector<int>& nums, vector<int>& seq, vector<bool>& used, int start) {
            seq.push_back(nums[start]);
            // 此时说明找到了一组
            if (seq.size() == nums.size()) {
                result.push_back(seq);
                seq.pop_back();
                return;
            }
            
            for (int i = 0; i < nums.size(); i++) {
                if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                    continue;
                }
                if (used[i] == false) {
                    used[i] = true;
                    backtracking(nums, seq, used, i);
                    used[i] = false;
                }
            }
            seq.pop_back();
        }
    public:
        vector<vector<int>> permuteUnique(vector<int>& nums) {
            result.clear();
            sort(nums.begin(), nums.end()); // 排序
            
            for(int i = 0; i<nums.size(); ++i)
            {
                if(i>0 && nums[i-1] == nums[i]) continue;
                vector<int> seq;
                vector<bool> used(nums.size(), false);
                used[i] = true;
                backtracking(nums, seq, used, i);
            }
    
            
            return result;
        }
    };

Leetcode 90. 子集 II

• 此题不讲究顺序，所以可以使用先排序再相邻去重的方式

  class Solution {
  private:
      vector<vector<int>> ret;
      // vector<bool> used;
      void backtracking(vector<int>& nums, vector<int>& ans, int start) {
          ans.push_back(nums[start]);
          
          ret.push_back(ans);
          for(int i = start+1; i<nums.size(); ++i)
          {
              if(i>start+1 && nums[i] == nums[i-1])continue;
              // used[start] = true;
              backtracking(nums, ans, i);
              // used[start] = false;
          }
          ans.pop_back();
          
          return;
      }
  
  public:
      vector<vector<int>> subsetsWithDup(vector<int>& nums) {
          sort(nums.begin(), nums.end());
          ret.push_back({});
          // used = vector<bool>(nums.size(), false);
          vector<int> tmp;
          for(int i = 0; i<nums.size(); ++i)
          {
              if(i > 0 && nums[i] == nums[i-1])continue;
              // used[i] = true;
              backtracking(nums, tmp, i);
              // used[i] = false;
          }
          return ret;
      }
  };

Leetcode 491. 非递减子序列

• 注意此题不能手动重新排序数组
• 因此需要防止同一层中出现重复的，使用set
• 每个递归函数自己定义自己的set，只考虑自己这一层是否出现过重复的

  class Solution {
  public:
      vector<bool> used;
      vector<vector<int>> ret;
      vector<vector<int>> findSubsequences(vector<int>& nums) {
          unordered_set<int> used;
          for(int i = 0; i<nums.size(); ++i)
          {
              if(used.count(nums[i]))continue;
              used.insert(nums[i]);
              vector<int> seq;
              recur(nums, seq, i);
          }
          
          
          return ret;
      }
  
      void recur(vector<int>& nums, vector<int>& seq, int start)
      {
          if(start>=nums.size())
          {
              if(seq.size()>=2)
                  ret.push_back(seq);
              return;
          }
          seq.push_back(nums[start]);
          if(seq.size()>=2)
              ret.push_back(seq);
          unordered_set<int> used;
          for(int i = start+1; i<nums.size(); ++i)
          {
              if(used.count(nums[i]) || nums[i]<seq.back())continue;
              used.insert(nums[i]);
              recur(nums, seq, i);
              // used.erase(i);
  
          }
          seq.pop_back();
  
      }
  };

Leetcode 40. 组合总和 II

• 注意此题的去重方法，是放在循环中
• 如果上一个元素与这个元素相等而且上一个元素与这个元素没出现在同一个数组之中
• 则说明在之前的某个位置，上一个元素必定在这个位置已经出现过了
  • 因为没出现过，意味着上一个元素与当前的这个元素在不同的尝试中被遍历过一次了，再来一次必然会重复

    class Solution {
    public:
        vector<vector<int>> ret;
        // vector<bool> used;
        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
            sort(candidates.begin(), candidates.end());
            vector<int> ans;
            // used = vector<bool>(candidates.size(), false);
            for(int i = 0; i<candidates.size(); ++i)
            {
                if(i>0 && candidates[i-1] == candidates[i])continue;
                // used[i] = true;
                traversal(candidates, target, i, ans);
                // used[i] = false;
            }
            return ret;
        }
        void traversal(vector<int>& c, int target, int start, vector<int>& ans)
        {
            ans.push_back(c[start]);
            if(target <= c[start])
            {
                if(target == c[start])
                {
                    ret.push_back(ans);
                }
                ans.pop_back();
                return;
            }
            for(int i = start+1; i<c.size(); ++i)
            {
                if(i>start+1 && c[i] == c[i-1])continue;
                traversal(c, target-c[start], i, ans);
            }
            ans.pop_back();
        }
    };

    Leetcode 93. 复原IP地址

• 注意此题的去重方式，主要是决定在哪个位置结束
• 注意，必须是前面明确声明要结束了的地址才可以作为答案之一
• 否则会重复

  class Solution {
  public:
      vector<string> ret;
      vector<string> restoreIpAddresses(string s) {
          string ans;
          // ans+=s[0];
          traversal(s, 0, 0, 4, ans);
          return ret;
      }
  
      void traversal(string& s, int start, int cnt, int remain, string ans)
      {
          if(start==s.size()&&cnt == 3)
          {
              if(remain == 0)
              {
                  ret.push_back(ans.substr(1));
              }
              return;
          }
          if(remain<0)return;
          if(start == s.size())return;
          
          if(cnt == 0 || cnt == 3)
          {
              ans+=".";
              ans+=s[start];
              if(s[start] =='0')  
              { 
                  // 结束本节
                  traversal(s, start+1, 3, remain-1, ans);
              }
              else
              {
                  // 结束本节，1个数字
                  traversal(s, start+1, 3, remain-1, ans);
                  // 继续本节，最少有2个数字
                  traversal(s, start+1, 1, remain-1, ans);
              }
              return;
          }
          else if(cnt == 1 || cnt == 2)
          {
              ans+=s[start];
              // 如果超出限制 则提前结束
              if(stoi(ans.substr(ans.size()-cnt-1))>255)return;
              if(cnt==1)
              {
                  // 在只有2个数字的时候结束本节
                  traversal(s, start+1, 3, remain, ans);
              }
              // 继续本节cnt = 2(本节有3个数字)或者cnt = 3
              traversal(s, start+1, cnt+1, remain, ans);
              return;
          }
      }
  };