PINEAL.ME   Archives  About

Basic Backtracking Problems

Introduction

Backtracking 类型的题目最重要的是想清楚每一层在做什么,以及到下一层一共有几个分叉。

时间复杂度: branch factor ^ level

时间复杂度: call stack -> level

Subsets

这一类的题目的框架为,在递归树中的第 i 层,代表正在处理 nums 里的第 i 个元素。 从该层的父节点一定会伸展出两个分叉: 第一个分叉代表着一层会放这个元素,第二个分叉代表不放这个元素。 这样出来的递归树非常平衡。

Subsets I

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> rst;
        sort(nums.begin(), nums.end());
        vector<int> cur;
        dfs(rst, cur, nums, 0);
        return rst;
    }
    void dfs(vector<vector<int>> & rst, vector<int> & cur, const vector<int>& nums, int level) {
        if (level == nums.size()) {
            rst.emplace_back(cur);
            return;
        }
        cur.emplace_back(nums[level]);
        dfs(rst, cur, nums, level + 1);
        cur.pop_back();
        dfs(rst, cur, nums, level + 1);
    }
};

Subsets II - Dedup

去重首先需要排序,要利用有序性。从递归树上看的话,放的那一个分支不变,因为我们是先做放元素,再走不放该元素的。如果不放该元素,那么此时的结果会跟父节点的是重复的。ab1 -> ab1b2, ab1。 a -> ab2, a。 ab1 和 ab2 不能同时出现。 所以这个分支就需要直接跳到跟当前层元素不同的那一层。在代码上体现就是level++。

ab1 ab2 出发产生的分支都是完全一样的。那么我们可以去掉ab2。

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> rst;
        vector<int> cur;
        sort(nums.begin(), nums.end());
        dfs(rst, nums, 0, cur);
        return rst;
    }
    void dfs(vector<vector<int>> & result, vector<int> & nums, int level, vector<int> & cur) {
        if (level == nums.size()) {
            result.emplace_back(cur);
            return;
        }
        
        cur.emplace_back(nums[level]);
        dfs(result, nums, level + 1, cur);
        cur.pop_back();
        //pruning techniques
        while (level < nums.size() - 1 && nums[level] == nums[level+1]) {
            level++;
        }                
        dfs(result, nums, level + 1, cur);
    }
};

Variant I - Combination

整体框架跟 Subset I 一模一样, 唯一的区别是 base case return 的时候加上条件: 当前结果的长度为 k 才返回。 原题链接:Combinations

去重的方法也应该和 Subset II 一样。

Variant II - Permutations of inserting spaces into a string

https://www.geeksforgeeks.org/print-possible-strings-can-made-placing-spaces/

Others

Permutations

因为全排列需要全部元素都出现,唯一不同的是他们的顺序,那么我们可以不停两两交换数组中的元素,得到全排列。

Time n * (n-1) * (n - 2) = O(n!)

Space O(n)

如果要求 一个长度不变的array/string 的 permutation 只是 order 不一样,就可以考虑用 swap-swap 的方法。

Permutations I

class Solution {
 public:
  vector<string> solve(string input) {
  if (input == "") {
    return {""};
  }
  vector<string> result;
  helper(result, input, 0);
  return result;
  }
  
private:
  void swap(string &s, int i, int j) {
    auto temp = s[i];
    s[i] = s[j];
    s[j] = temp;
  }

  void helper(vector<string> & result, string & s, int index) {
    if (index == s.size()){
      result.emplace_back(s);
      return;
    }
    for (int i = index; i < s.size(); i++) {
      swap(s, i, index);
      helper(result, s, index + 1);
      swap(s, i, index);
    }
  }
};

Permutations II - Dedup

class Solution {
 public:
  vector<string> solve(string input) {
    vector<string> result;
    helper(input, result, 0);
    return result;
  }
  
private:
  void helper(string & input, vector<string> & result, int level) {
    if (level == input.size()) {
        result.emplace_back(input);
        return;
    }
    
    set<char> charset;
    for (int i = level; i < input.size(); ++i) {
      if (charset.find(input[i]) != charset.end()) {
        continue;
      }
      charset.emplace(input[i]);
      swap(input[i], input[level]);
      helper(input, result, level + 1);
      swap(input[i], input[level]);
    }
  }
};

Parenthesis Problems

Valid

Given N pairs of parentheses “()”, return a list with all the valid permutations.

分析:

void validParenthesisHelper(int l, int r, int n, string & cur, vector<string> & res) {
    if (l + r ==  2 * n) {
        res.emplace_back(cur);
        return;
    }
    
    if (l < n) {
        cur += "(";
        validParenthesisHelper(l + 1, r, n, cur, res);
        cur.pop_back();
    }
    
    if (r < l) {
        cur += ")";
        validParenthesisHelper(l, r + 1, n, cur, res);
        cur.pop_back();
    }
}

vector<string> validParenthesis(int n) {
    vector<string> res;
    string cur;
    validParenthesisHelper(0, 0, n, cur, res);
    return res;
}

void testvalidParenthesis() {
    auto res = validParenthesis(3);
    for (const auto & str : res) {
        cout << str << endl;
    }
}

Time: O(2^2n) Space: O(2n)

Coin Combinations

99 Cents

https://www.geeksforgeeks.org/find-minimum-number-of-coins-that-make-a-change/

void coinCombinationHelper(const vector<int> & coins,
                           vector<vector<int>> & res,
                           vector<int> & cur,
                           int remaining,
                           int level) {
    if (level == coins.size()) {
        if (remaining == 0) {
            res.emplace_back(cur);
        }
        return;
    }

    int n = remaining/coins[level];
    for (int i = 0; i <= n; i++) {
        cur.emplace_back(i);
        coinCombinationHelper(coins, res, cur, remaining - i * coins[level], level + 1);
        cur.pop_back();
    }
}

vector<vector<int>> coinCombination(const vector<int> & coins, int target) {
    vector<vector<int>> res;
    vector<int> cur;
    coinCombinationHelper(coins, res, cur, target, 0);
    return res;
}

void testCoinsCombination() {
    vector<int> coins = {25, 10, 5, 1};
    auto res = coinCombination(coins, 99);
    for (const auto & v : res) {
        for (const auto & c : v) {
            cout << c << " ";
        }
        cout << endl;
    }
}

find all valid combinations of factors that form an integer

https://www.geeksforgeeks.org/given-array-strings-find-strings-can-chained-form-circle/

Backtracking on Tree

Longest consecutive sequence

int global_max = INT_MIN;

int helper(TreeNode* root) {
  if (root == nullptr) {
    return 0;
  }

  int left = 0;
  int right = 0;

  if (root->left && root->left->val -1 == root->val) {
    left = helper(root->left);
  } 
  if (root->right && root->right->val -1 == root->val) {
    right = helper(root->right);
  } 
  int local_max = max(left, right) + 1;
  global_max = max(global_max, local_max)l
  return local_max;

} 
search   DFS   backtracking