How to solve the combination problem in leetcode

This article will explain in detail how to solve the combination problem in leetcode. The editor thinks it is very practical, so I share it with you as a reference. I hope you can get something after reading this article.

Topic link

Https://leetcode-cn.com/problems/combinations/

Topic description

Given two integers n and k, return 1. The combination of all possible k numbers in n.

Example:

Input: n = 4, k = 2 output: [[2Jing 4], [3Jing 4], [2jue 3], [1jue 2], [1Jue 3], [1pr 4],] solution ideas

Tags: backtracking and pruning

N represents a range of 1. N balance represents the remaining space, start represents the start position, and list represents the backtracking list.

Judge balance = = 0. If 0 means k has been saved in list, copy list and store it in the result ans.

If it is not 0, the recursive call starts from the start location, and now the current location data is added to the list and goes to the next layer. After waiting for the return, the data added by this layer is removed, which is essentially the process of constructing the tree.

The end condition of the loop defaults to the maximum value of n, and pruning can be optimized here. For example, if the list starts with start=3, that is, [3], then the combination must not exist, because at least 3 data are needed, so the critical point of pruning is n-balance+1.

Graphic illustration

Code class Solution {private List ans = new ArrayList (); public List combine (int n, int k) {getCombine (n, k, 1, new ArrayList ()); return ans;} public void getCombine (int n, int k, int start, List list) {if (k = = 0) {ans.add (new ArrayList (list)); return } for (int I = start;i